And you're taking a typical American point of view on who is an evil doer (though Hitler is a universal choice).
By the way, Genghis Khan was religious. Actually he was a true master of war. He didn't need to use religion and declare a "holy war" to move his troops around Europe and Asia.
Really? If he convinced his foot soldiers to die for his cause, then there are only two possibilities. Either his forces were strong enough to turn any battle into a cakewalk, or he used religious rhetoric and imagery.
My own pet theory is that patriotism is the penultimate refuge of a scoundrel. Religion was invented when patriotism proved insufficient to the task.