1) Hit mechanics. When you do damage to someone, it should make them recoil. Always, with exceptions only in very specific circumstances. Same when someone hits you. Put in those five frames of universal hitstun on impact to lend weight to those hits. Nobody's attack pattern survives taking a solid hit mid-combo. Contrast with any game where an attack lands, but the recipient simply continues with their current action without so much as a pause frame, and you can immediately feel the difference. Some games allow that as a mechanic, but even then, something as simple as a bit of hitstun can make a huge difference. Seeing an attack land on the Hulk and having that fraction of a second to realize it hasn't stopped his haymaker gives you that instant, as a player, to lose your shit before Hulk pushes it back in. On the other side of the coin, the complete lack of tangible contact in MKX or Injustice can be really frustrating, because other than a small tick of your opponent's health bar and the fact that their sprite is flashing, it looks like they literally just walked through your attack. Because, for most intents, they did.
2) Collision detection. BamHam (and most games with grappling) cheat on this. Obviously, being able to make your hitboxes and hurtboxes connect cleanly is important, but the graphical complexity that comes when 3D models do any sort of grappling means that everything has to be perfectly choreographed or you end up with clipping errors that look like they should be instantly fatal. Hits should be hits, throws should be throws, slams should be slams, and there should be no ambiguity as to how an attack will play out if successfully executed. If players want to roll dice for every attack, there are plenty of functional, existing systems to let them roll dice for every attack. If players want to actually press buttons for every swing, then their own decisions and their targets' reactions should be the only factors determining the outcome.
3) Animation. Attention to detail is key here. Weight, acceleration, transfer of energy, and aesthetics all count for something. The way BamHam handles things, in a manner that specifically suits Batman as a character, is that he has extremely little start-up on his counters–one second, the thug's fist is halfway to Batman's face, the next, the thug's got four broken fingers and is dining on sidewalk. This approach doesn't work so well with characters that aren't meant to be brooding, dangerous martial arts masters, but considering how many video game characters these days seem to be just that, it's surprising that it doesn't get more play. For other examples of animation done right, check out Aki's N64 wrestling games–the effort and detail they put into the animation, from the punches to the slams to the ways the wrestlers would writhe in pain or recover slowly after they'd taken big damage, was groundbreaking for its time and remains impressive to this day.
4) Responsiveness and challenge. This is the big tradeoff, and it's extremely important to know where you stand before trying to jump in. BamHam is responsive. Again, counters are extremely powerful, and you can get into a counter stance so quickly as to make the game laughably easy if you fight purely defensively. Devil May Cry is responsive. Bayonetta is responsive. All of these games let you do whatever you want, when you want, and if you get hit, it's your own fault. The challenge in this particular design lies in taking away that responsiveness at very deliberate, very fair times. Batman can counter at the drop of the hat, but he can't cancel out of his own attack animation to do so. Get carried away with your combo, and you open yourself up to someone else. DMC lets you use the Stinger to get into a fight, chase down enemies, or simply punctuate a combo, but especially if you whiff, there's that moment of vulnerability where you can get smacked for not planning ahead. Middle Earth: Shadow of Mordor takes the BamHam combat system almost in its entirety, but crucially allows you to cancel out of any attack to immediately counter, and just that small change alone removes almost all remaining challenge from the game's melee.
Putting all of these together is where things can get difficult, but playing with the knobs a little can yield drastically different, but still very satisfying results. Want a burly bruiser who has attacks with slow windup, but tons of damage, the ability to ignore limited hitstun, and big knockback/knockdown on his attacks with the ability to follow up with ground slams? Want a lightning-fast needler who only generates hitstun on every third hit of his combo, but has abusable i-frames and the ability to string together an absurdly long chain of attacks? Want a counter king whose attacks are utterly devastating as long as they land during the opening frames of an enemy's attack animation? Fucking do it.