Deleting millions of files from a directory can be a daunting task. rm -rf will expand the to glob every file in the directory and return an error such as "Argument list too long". find . -type f -delete will try to get a list of all files before deleting them, and is very slow.
The answer is to bypass BASH completely:
perl -e 'chdir "BADnew" or die; opendir D, "."; while ($n = readdir D) { unlink $n }'
Thanks to Randal L. Schwartz