TOS said "Under his rule". Which tells his nothing of the nature of his rise to power.
It was also stated that he wasn't the only one to rise to power.
Spock: In 1993, a group of these young supermen did seize power simultaneously in over forty nations.
McCoy: The last of the tyrants to be overthrown.
Kirk: He was the best of the tyrants, and the most dangerous.
Maybe all those deaths weren't caused by Khan, but the other tyrants.