I've never worked on an FPS and I've worked on many games with third-person melee combat (Die By The Sword, Draconus, Spider-Man 1 & 2). Maybe it's just grass-is-greener syndrome, but I have the feeling that making a fun FPS is just easier. Consider some of the differences:
Skill game: suppose you take away all the trappings from an FPS - you have one gun with unlimited ammo and you never get to change. Still, at its core, you've got an aiming game, something which a player can become skilled at. You take away all the different moves and blocks from a fighting game, and you've got a button masher - who can hit the button the fastest?
Easier to make terrain matter in an FPS: cover's important in an FPS. It's hard to make terrain matter in melee combat. Usually terrain is just annoying, and brawlers tend to place the action in open arenas free from obstructions.
Ammo: once you do bring the multiple weapons into an FPS, they typically have ammo. With the exception of Deus Ex 2, where they made the risky move of giving you universal ammo, and games where they just leave too much ammo lying around, this automatically forces the player to try all the weapons, whether they're correctly balanced with each other or not. Compare with the moves from a fighting game - players very quickly find a favorite move, and tend not to try new moves, even though they may be bottom feeding (they could do a lot more damage against particular enemy X if they'd just experiment).
These problems are solvable and maybe the visceral thrill of melee combat, that being-in-somebody's-face-and-hitting-them-with-something-heavy, make it worth it, but I do wonder if a game in the God of War camp will ever be able to really compete with a game in the Halo camp.