Já considerou tar
de todas as coisas? Soa bobo, eu sei. Tente isto:
$ cd /path/to/my/source/files
$ tar -cf - . | tar -xvf - -C /path/to/my/destination/files
Deve funcionar surpreendentemente bem com muitos arquivos pequenos - melhor que rsync
certamente.