Gunstar Heroes (1993) is widely considered to be one of the best action games on the Sega Genesis — ironically, being commercially unsuccessful due to poor promotion. It features a variety of melee attacks, as well as 4 basic weapons which you can combine in pairs (making a total of 14 combinations) — all densely packed in a swift and explosion-heavy gameplay spanning over seven uniquely designed stages.
This single-player run by Jackic plays through Normal difficulty. Among other changes, in Normal difficulty, weapons do more damage, and the boss of the second stage has fewer forms. For a two-player run on Expert difficulty, see this movie.