I have tested shutil.rmtree() with a large number of files using modified benchmark from issue28564. For 400000 files it takes less than 5 seconds. From the comment to the coreutils benchmark (http://git.savannah.gnu.org/cgit/coreutils.git/commit/?id=24412edeaf556a):

# Using rm -rf to remove a 400k-entry directory takes:
# - 9 seconds with the patch, on a 2-yr-old system
# - 350 seconds without the patch, on a high-end system (disk 20-30% faster) threshold_seconds=60

Running the coreutils benchmark gives the result 3 seconds on my computer.

It seems to me that this issue have been fixed in the kernel.