Why is everyone in Echo who isn't a mage scared shitless of Max's Mantle of Death? Sure, it means he can kill people but everyone in SI can do it just as well, and Max is not known for going on regular public killing sprees.
Because there's huge difference between someone who can kill you, but probably won't, and someone, who can accidentally kill you just because you were unlucky to be near him and born under the light of wrong stars. That's what the title Death on King's Service means - someone who has no complete control of his lethality, mild version of Walking Wasteland. Both Max with his toxic spit and Mad Fishmonger with his gloves and hair-trigger temper were, at least for government and people, such persons.