Ehh, rm -rf is pretty much your best bet. What error are you encountering?
Two things you can try.
If all your files you want deleted are in one directory, try rm -d This will unlink the directory, you need an older version of coretuils to do this however, I think it was removed in releases after 6.x. A caveat you are going to encounter with this method is all those files are going to end up in lost+found and will need to be cleaned up by an FSCK at some point.
Second options, and probably not recommended, would be to nice the rm -rf process to a higher priority. Sure your system will probably become unresponsive until the delete is done, but it will most likely finish faster.
Post the error you are getting and we can dig into it a bit..