Within cinder.conf there is a setting for wiping the old volumes when they are deleted. The default is to overwrite the entire volume with zeros. This means the larger the volume, the longer it takes to delete it. This process can take far longer then creating the volume, as creating the volume, cinder only has to allocate the appropriate space, not actually put any data in to it.

# Method used to wipe old voumes (valid options are: none,
# zero, shred) (string value)
#volume_clear=zero

# Size in MiB to wipe at start of old volumes. 0 => all
# (integer value)
#volume_clear_size=0

Change the values to either none to remove the wipe, or change the volume_clear_size=50 to only overwrite the first 50mb of the volume, thus wiping the partiton table if there is one.