Not quite. It does bonus damage but its not the same as a critical hit. Meleeing someone from behind does 2x damage. Melee base damage is 100 so it does 200dmg. One thing I've noticed that bugs me about melee though is that the animations are kind of off on some of the classes. If you melee repeatedly sometimes it'll keep doing damage but not play the animation every time.
The damage on melee from a sin is not a joke. If you got ambushed you deserve to die. Pay more attention or don't wander around like it's some kind of solo killfest. Solo play is for assassins. Though i did work as a tandem with one the other day and the other team had a nice big steaming hot cup of RAGE. Other classes? Not really sure. I play a low HP class, so... yeah. I assume All-Star is that icon next to player level? I'm.. level 50 or something i think. Haven't had as much time to play as i'd like (Work is fun like that) But i do know that all-star doesn't mean good, doesn't mean bad, doesn't mean nice. Just means experience. I do love making people rage, it amuses me people get so worked up... but it's better when they don't drag the server down and make people quit because of it.
The last match of MNC I played I used gunner and tried melee-ing groups of bots before I killed them and mortared groups of bots that had players following them. Not only was I alive longer because I was able to suppress enemy actions from a range bit I got more juice to trash their higher level turrets
Gunner's Mortar fired into a group of bot nets you a pretty decent amount of juice, and if you pick up the juice boxes you just about have a full bar.