The example code was running on Windows, not Unix.
However your other points are true. I admit that I am guessing as to how the Windows dir function is running so much faster than the simple Perl shown.
But one note. It may be that your filenames don't divide well based on the first few characters. (So one directory has a ton of directories, the rest do not.) In that case the above scheme can be improved by first taking an MD5 hash of the filename, and then placing files into directory locations depending on the characters in the MD5 hash.
(-:At which point your on-disk data storage is starting to be a frozen form of efficient data structures you might learn about in an algorithms course...:-)