I got to thinking about octopuses as characters in video games- retro in particular. Off the top of my head, I can think of the following games that have octopuses:

Super Mario Bros.
Zelda
Adventure Island
Parodius
Genji Tsuushin Agedama (a really delightful PC-Engine platformer/shooter with a rail gameplay system that was based on an anime- check it out)

Can you think of any others not listed? Thanks!