Cheep-Cheep?
 

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.

Re: Cheep-Cheep?
 

You're probably thinking of Big Bertha, not Cheep-Cheeps

Cheep-Cheeps are small fishies that cannot eat you
However, Big Bertha can
http://img187.imageshack.us/img187/499/bertha7vz.png

The similarities are striking, but I don't think they are related.

Re: Cheep-Cheep?
 

You're right (obviously).
I just read the comment for the video, and apparently didn't read Wikipedia very well, because it does mention both by their proper name.

Their respective colours are pretty much opposite, but they're both bulbous fish, seemingly without scales (more of a dolphin-like skin I'd guess), with buckteeth... or tooth in Bertha's case?
They are both at least half head/mouth, and neither looks particularly bright.
The swallow-you-whole-and-kill-you-instantaneously thing they have in common as well.