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.