Cleaning /tmp on booting needs too long/can block the booting process

I'm using Ubuntu 15.04 dev with mountall 2.54ubuntu1 and for some tests I have created the directory /tmp/test with 1 million empty files in it. As I'm using a hard disk drive the next boot has needed ~25 minutes mainly to cleanup /tmp/test. I'm seeing 2 problems here:

- The cleanup process has needed a too long time. If I'm recreating /tmp/test with 1 million files, dropping the caches with "echo 3 > /proc/sys/vm/drop_caches" and executing "rm -fr /tmp/test" the cleanup needs only ~3.5 minutes so maybe something can be enhanced here.
- The cleanup process blocks the booting process so the user can't login until it has finished. Even with such a performance optimization from above this can still become a problem in some cases. Maybe on the booting process /tmp could be renamed to /tmp.old and a new directory for /tmp could be created as this is very fast even with a bloated /tmp. The booting process can then continue and /tmp.old could be deleted asynchronously in the background (maybe with low priority).