Perforce only scans through everything when you update or scan for changed files, but mostly tracks changes file by file. Git (and mercurial) work with the state of the tree as a whole for most operations, because this makes handling searching, branching, merging, etc. much nicer, but it means that when you have gigantic binary files just sitting around, it takes time scanning them as well.

Why not cache the MD5/SHA1 hashes and only update them when the timestamp of the file changes?

Mercurial does, by default. I'm almost certain git already does, too.