The main menu itself is actually just a regular level, and the logo is made up of many smaller individually-made tiles. I wanted a main menu that didn't look like a PuzzleScript game, so I'm happy to hear the sega genesis/mega drive comparison!
As for the in-game menu, it's pretty much just a whole bunch of individual tiles that are populated on the screen, and some semi-transparent tiles everywhere to give it that 'darkened' effect. The player movement is disabled, and is instead transferred to the menu dots until the action key is pressed again.
Both are pretty hacky solutions, but gives the cool illusion of actual menus!