I have done 700k and 800k files transfers (including hardlinks), but indeed it could take a while to compute the transferlist. Newer rsync versions bring down the amount of memory needed drastically. That is one of the reasons I offer a recent rsync in RPMforge. There is almost never a good reason to use a dated rsync.
i have used rsync on ~16million files with a filesystem size of about 1.5TB - worked fine but took a while