I think it depends on how they are implimented.
Backup melee attacks such as the knife in CoD or the gun-whack in Halo are easy to abuse since they allow an easy one-hit kill on demand without much in the way of a sacrifice or tradeoff (you can hold you gun steady one moment, slash someone's nipples off the next and then be back in a perfect firing stance before anyone can react).
Dedicated melee weapons (such as the knife in Turok or the crowbar) feel more fair in my opinion since you trade the capacity to fire back for a guaranteed close range one hit kill (and in some cases a speed boost) that would encourage bith the 'weapon of last resort' behavior that games like Call of Duty attempt to emulate and the 'berserker' type of approach that is fitting in games like Turok or Unreal Tournament.