The pejorative phrase somewhere to the right of Genghis Khan and variants mean extremely or fanatically right-wing or reactionary in one’s political or personal beliefs.

This phrase associates right-wing views of the most extreme kind with the supposedly barbaric and tyrannical rule of Genghis Khan (born Temujin – 1162-1227), the founder of the Mongol empire; he took the name Genghis Khan (meaning ruler of all) in 1206 after uniting the nomadic Mongol tribes, and by the time of his death his empire extended from China to the Black Sea—biography: Oxford Dictionaries.

In Who was the most right-wing man in history?, published in The Spectator (London) of Saturday 25^th February 2006, the English journalist, author and historian Paul Johnson (born 1928) proposed the following explanation:

The phrase is often used by thoughtless people, TV interviewers, tabloid columnists, etc. ‘He is even to the right of Genghis Khan.’ The implication is that Genghis Khan is on the extreme right of the political spectrum. What is the origin of this belief? And when did the phrase come into use? I believe it is hardly more than half a century old. Hitler, again, is to blame. He is seen, falsely, as the epitome of ‘the Right’. He is also seen, more accurately, as a mass killer on an unprecedented scale. Before the 20^th century, the classical perpetrator of terrorist massacre, pillage and the destruction of cities was Genghis Khan. He was not, however, seen as a political figure of either left or right — just as a savage barbarian. Hitler, however, was linked with him as a mass killer, and therefore Genghis took on Hitler’s political colouration.

The earliest instance of the phrase that I have found is from The Philadelphia Inquirer (Philadelphia, Pennsylvania) of Saturday 2^nd November 1963, which published an article titled Starling Battlefront: Birds Called Asset To City Hall; ‘Red’ Linked to Fowl Deeds, about the plan to drive the starlings from City Hall with electricity:

The $95,000 Starling Shocker System for City Hall—good or bad? Residents expressed differing opinions with so much vigor Friday they drowned out the sound of the chirping birds themselves.
[…]
W. Itch Hunt, president of the Samuel Oak Society, Philadelphia Chapter, professed to see “fascist dogma” in the pronouncements of the anti-starling partisans.
“I don’t often joke,” he said, “but I really think there should be less dogma and more birdma.” He said H. Oppingmad, head of the Society of Citizens Ranting for Abolition of Moochers, appeared to be “somewhat to the right of Genghis Khan.”

The name of Attila (406-53), king of the Huns (434-53), who ravaged vast areas between the Rhine and the Caspian Sea, is sometimes substituted for that of Genghis Khan in this phrase. The earliest use that I have found of this variant is from Dissent Talks Begin in KC, published in the Springfield Leader and Press (Springfield, Missouri) of Friday 14^th February 1969:

Kansas City (AP)—Rep. Allard K. Lowenstein, D-NY., emphasized the tactics of dissent Thursday night and the right of those who see the need for dissent “to respond to conscience.”
The first year congressman was the keynote speaker at the University of Missouri-Kansas City Robert F. Kennedy Memorial Symposium on Dissent. […]
Lowenstein criticized Congress for “selecting leadership by seniority status.” He said that in the House rules committee three Mississippians “whose positions are somewhere to the right of Attila the Hun” hold the power.