The module does not calculate an MD5 for every file, as that would indeed be hugely wasteful. It does a first pass where it discards all files that are not of identical size. Only the files that remain are checksummed for a more detailed comparison. (I am certainly open to any patches that can make that process even quicker).
This was actually pointed out in my response to ClÃ¡udio's email, but as he didn't send his email via rt.cpan there is no public record of that.