This question made me think of all the damage that Superman could do by himself if he wanted cough Man of Steel cough, so I tried to strip his list of powers down to the ones that by themselves would make him an unstoppable murderer.
These 3 seemed like the bare minimum:
1) Invulnerability. He can go about doing whatever he wants if bullets, knives, whatever can't pierce his skin and/or do damage.
2) Super strength. If captors (police, military, other super heroes) somehow subdue him, this would allow him to break out of any prison/containment.
3) Not needing to eat or breathe. Note that this is apparently a feature of Silver Age Superman, and not recent incarnations. Either way, if he doesn't require air/food/water, then he can be kept in prison indefinitely, and he can break out at his own convenience to resume his murder spree.
Being essentially unable to die, able to withstand any attempts to stop him, and being capable of breaking out of any imprisonment, it seems that you could get away with unlimited murder until you die of old age. With powers that can be used defensively like this, he is free to murder in any way he pleases (guns, knives, bombs, strangling, drowning, you name it) and can't be stopped.
Alternatively, if you wanted to stick to just 1 ability instead of 3, you could give him something on par with Deadpool's healing factor and accomplish much the same thing, although avoiding capture/imprisonment would be harder with just healing and not super strength.