Allying with muslims doesn't lower the pope-meter.

Historically Chingis Khan were very tolerant of the religious beliefs of his conquered subjects. He slaughtered cities that offered resistance but incorporated those that surrendered into his empire with very few strict rules - give him soldiers, give him money, and be loyal, or face eradication. He was well known for quckly learning from his enemies, and adapted siege technology for example from the Chinese and Muslims.