but a good image compression algorithm could find these repeated patterns and store them only once. If anything, I would expect that this image compressed by a modern algorithm would be much smaller than the original game.
It really can't, not in a way that would allow the image format to be generic enough. Remember that PNG is used for trillions of images, whereas SMB has the luxury of only caring about a limited set of colors, and of having a Sprite engine available in the console itself to help optimize it all.
You're looking at a lot of procedural data where for example the patterns behind the sprites can change without having to create a new sprite. Where the palettes were separate from the image data so they could look different without having to use double, triple the storage. These things can't be picked up on by png, it's not a smart enough format to be able to arbitrarily detect all repeated patterns of varying sizes and turn them into what amounts to a procedural level script.
I can't find a good exhaustive sprite sheet of SMB (this is the best I can find, but it contains a ton of repeats: https://www.mariouniverse.com/sprites-nes-smb/). I'd love a visualization of just how tiny SMB is in terms of what's stored in it.
A good image compression algorithm could. PNG just isn't smart enough for this purpose. One could argue that the NES code and PPU data itself constitute a very efficient compression scheme for compliant images, albeit human-crafted rather than algorithmic. IOW, it's unlikely any automatic compression scheme will outperform simply running the SMB program.