Linux – How to remove a very large folder (~40GB) with lots of files efficiently in Linux

I'd like to remove a folder with lots (millions) of files efficiently. When I issue rm -rf folder/, it takes hours, and I have to kill it. I'm wondering whether there is a magical way of doing this faster?

Another thing is when I want to get the size of the folder with du -hs folder/, it also takes a very, very long time. I was never patient to wait for it and killed it after several hours.

Thanks.