I never really played any Mario games (just Mario Bros. (Atari) and Wario Land 2 or something), so maybe I'm stating something really obvious.
I just saw
this movie, and the fish reminded me of the Dopefish, who I am much more familiar with.
According to
this Wikipedia article it was actually in the original Nintendo Super Mario game, a big piece of inspiration for the Commander Keen games, although I have no idea how similar it was in that incarnation.