The quote comes from the English translation by John Andrew Boyle of The History of The World Conqueror written by the Persian historian Ata-Malik Juvayni in the 13th century.

According to Juvayni, in about 1218, three merchants from the muslim West came to trade fine clothes with Genghis Khan. However, they tried to swindle him, demanding three balish of gold (1 balish being 2,000 dinars) for fabric that cost him ten or twenty dinars at most. Genghis Khan was outraged, took all of the merchant's wares as plunder, but then overpaid them in silver and gold and sent them on their way. At the same time, he told his sons and men to gather up 450 men, give them a balish of gold and silver each, and told them to go west and buy wares from the Muslims, so "that henceforth the abscess of evil thoughts may be lanced by the improvement of relations and agreement between us, and the pus of sedition and rebellion removed".

The party made their way to the city of Otrar, once a bustling city along the Silk Road, today a ghost town in southern Kazakhstan. One of the merchants knew the governor, and addressed him by name (Inalchuq) instead of title (Ghayir-Khan), and the governor was so outraged and embarassed that he arrested them and wrote to the Sultan about the episode. It didn't hurt that he wanted all that silver and gold as well. The Sultan in faraway Iraq allowed the Ghayir-Khan to take their lives and property, which he did, post-haste.

However, one of the merchants managed to escape and report back to Genghis Khan, who was so enraged he went up a hill to pray for three days and nights, "I was not the author of this trouble, grant me strength to exact vengeance".

(Juvayni had a flare for the dramatic. He also estimated the Mongol army to be 700,000 strong, about seven times that of other historians)

And so he mustered up an army, but sent an envoy ahead to warn the Sultan of his intentions. So when Genghis Khan started his journey of bloody retribution, Ghayir-Khan was there waiting for him, with sixty thousand well-equipped men who knew surrender was not an option. But they were still no match. The Mongols thoroughly levelled the city, and captured the locals, as levy or tradesmen.

But anyway, that's not your question. Genghis Khan's lust for bloody was hardly sated, and so he continued conquering city after city, until he came upon the land of Transoxiana and its two jewels: Samarqand and Bokhara, the City of Learning. Instead of sacking the closer, larger Samrqand, he crossed the seemingly impassable Kyzyl Kum desert, laying siege to the completely unprepared Bokhara. After three days, twenty thousand men, led by Keshili-Khan and Kok-Khan--who was a Mongol defector, rode out to meet Genghis Khan. The results were so bloody, "from the reflection of the sun the plain seemed to be a tray filled with blood." Bokhara, horrified and defeated, surrendered.

Genghis Khan rode into the city, demanded all the grain, wine and singing girls, and trampled the leaves of the Koran under their horses' hooves, etc. etc. before climbing the pulpit of the musalla (open area in front of a mosque), gathering the 280 richest men in the city before him, and declared:

O people, know that you have committed great sins, and that the great ones among you have committed these sins. If you ask me what proof I have for these words, I say it is because I am the punishment of God. If you had not committed great sins, God would not have sent a punishment like me upon you.

The sins were, ostentatiously, the murder of his caravan a year earlier, and the punishment, on top of all the bloodshed and enslavement commitment, was all the money of the wealthy men thus summoned.

As to what god? Genghis Khan wasn't picky. He was Tengrist, but his mother and daughter in law were Nestorian Christian, and he consulted Buddhists, Muslims and Taoists alike. Given Juvayni's love for flowery speech, and that he was working off of decades-old first- and second-hand accounts, it could just be an embellishment on the author's account. Given the context, the religious aspects of the speech don't matter--the entire speech is a pretty transparent grab for money with a side of victim-blaming.