Using rsync is surprising fast and simple.
mkdir empty_dir
rsync -a --delete empty_dir/    yourdirectory/
@sarath's answer mentioned another fast choice: Perl! Its benchmarks are faster than rsync -a --delete.
cd yourdirectory
perl -e 'for(<*>){((stat)[9]<(unlink))}'
Sources: