1) Have him change his alignment to evil
2) Make sure future NPCs are more personable so the players are more likely to feel like they are people
3) Use reputation, also for the good PCs, give them rewards, explicitly tell in NPC character that Mr Murderhobo is not trusted because he's a cold blooded killer

This should help him with a) getting it out of his system and b) having some closure when you kill the PC, all murderhobo PCs should find the same ending: death.