I thought there was some ext4 specific mount option you could set to tell it to speed that up significantly? I can't seem to find it now.

In any case, the classic workaround (which can be a PITA) is to create a tree of subfolders and distribute files between them. E.g. first letter of filename, second letter of filename, or for more even distribution use first characters from hashing the filename.