In my opinion, the fame isn't really an issue. As long as the fame is either attributed to whatever pseudonym he works under, or he just uses false identities, such that someone who knows his work still can't track him down and arrest or kill him, it shouldn't be a problem.
Not sure on the "killed every responsible" matter. I mean, Murdoc does have a point that he'd have trouble killing all of them in their sleep. But... he definitely could kill them all some other way.
If he did manage to get trusted enough to run operations with them, he could just purposely botch it or betray them. Doesn't even matter if they don't all die, so long as none escape, seeing any survivors who get incarcerated could just be picked off at his leisure while being transported or somesuch, assuming of course that other underworld figures who want them dead for one reason or another, doesn't just arrange for them to get shanked a few dozen times.
Or he could recruit some of the other people they conscripted and who would likely still have quite the grudge as well, to help with the whole "murder everyone" plot. Or he could just betray info to people who want them dead, and let them handle it.
Basically, there's plenty of ways to kill them all, and honestly, it could be a lot more interesting keeping it as him having killed them all a long time ago. IT raises a lot of questions of why he's still in the business and his motivations, which would likely be something more complex than simple revenge seeing as the people responsible are all in shallow graves now.
However, you probably should reduce his kill count by an entire order of magnitude. By my calculations, from the age of 13, he'd have to kill just over one person every four days. I mean, he could certainly rack up that many kills by shooting random people and escaping with his cloaking unit, but he probably isn't shooting random people for no pay. Just communicating with his client could take a week if not more, and tracking down his target and planning out his killing would presumably take plenty of time as well, along with getting in and out of the country (since he'd likely need to get false documents and either smuggle in his weapons somehow or acquire and dispose of them). Realistically speaking, it could take months.
Oh also, the whole "in the top 3 snipers" statements is probably setting off a few people's Mary Sue alarms, you probably could safely remove that anyway seeing as it's already quite clear he's good at his job.