There was also Zero Tolerance on the Megadrive which also came with a link cable to go from one joypad port to another on a different console.
Also in terms of Fps games there was something on the C64 around '87-'88 that used something like filled polygons. I can't remember that name of the game but if my memory serves me correctly it was released by Rainbow.
The first console FPS (like Wolf3D or Doom) would probably be Corporation aka Cyber Cop, originally released on the Amiga in 1990, ported to the Genesis in 1992. Corporation was also very advanced for its time, it had dynamic lighting, realtime gameplay and maze-like environments (couple of years before Wolfenstein) but also had more complex elements like RPG stats and inventory/equipment and is probably the first FPS to have hacking and sneaking mechanics. It's the grandaddy of System Shock in some ways.
Regarding FPS games in general, or at least first person games on home computers, you could probably go as far as '82 with Wayout, a maze game with realtime first person graphics. Its "spiritual sequel", Capture the Flag (1983) is probably the earliest example of a FPS with split screen multiplayer and something that resembles the CTF game mode (although you just need to touch the flag, not take it back to your HQ).
Mercenary (1985) introduced an open world, a city you can walk, drive or fly around in, take and give items, destroy buildings or other vehicles, talk to NPCs, "work" for two sides, earn money and it even had a sprawling underground complex you could enter via elevators.
Then there's The Eidolon (1985), an adventure FPS where you battle mythical creatures by throwing magic with various effects and explore fractally generated caves.
And then there's MIDI Maze for the Atari ST (1987) and Driller released the same year. MIDI Maze is probably the earliest example of realtime FPS deathmatch and team deathmatch, sporting up to 16 player local MP with Atari STs linked via the MIDI port, a LAN party.
Driller (Space Station Oblivion) was more of a first person adventure/puzzle game, had full shaded polygon graphics, goals to solve and even secret rooms and hidden levels. Its sequel, Dark Side (1988) is more advanced, and probably the first to have a jetpack in an FPS game as well as a "stance" icon displaying if the player is on foot or in the air with the jetpack on, years before modern military shooters.
These are all games that control a character on foot, which is one of the key aspects of classic FPS games. There are even earlier examples of first person games with shooting which were largely set into a cockpit of a vehicle (Battlezone, Star Wars and so on).