In hindsight with the success of the Genesis and the Altered Beast pack-in, Legendary Axe definitely makes the most sense. NEC was looking at the past success of Nintendo's pack-in instead, and probably underestimated SEGA at the time considering the PC Engine was trouncing the Mega Drive back in Japan.
My problem as a kid with Keith is the game you buy is not the game you play. The box looks like some epic hack and slash with a muscular, Conan-esque warrior (like your Rastans, Rygars or Wizard and Warriors) but instead you're this slow, spikey haired dude, and then you're in a mech suit. The false advertising really just emphasized what the game WASN'T rather than what the game really was, which is a fun but eccentric little action platformer.