Milhões de arquivos em um diretório são design ruim e serão lentos. Subdivide-os em diretórios com menor número de entradas.
Dê uma olhada no link
Use RAID e / ou SSDs. Isso, por si só, não resolverá os tempos de acesso lentos, mas se você introduzir vários diretórios e reduzir o número de arquivos por diretório, digamos, por uma ordem de magnitude ou duas, ajudará a evitar pontos de acesso.
Considere o XFS, especialmente ao usar várias unidades e vários diretórios, isso pode proporcionar bons ganhos (veja, por exemplo, este thread para opções de uso. Ele dá algumas dicas para o XFS em md
RAID).