I don't think rm is a proper tools for millions of files. I suggest using rsync to do this.
First, you need to create an empty directory, and then rsync the empty directory to your directory.

mkdir empty_dir
rsync -a --delete empty_dir/ yourdirectory/

This will be very fast -- faster than other approaches listed here, like find+xargs or find -exec rm.