Having just (I mean within the hour) finished Jack Weatherford's "Genghis Khan and the Making of the Modern World" I feel incredibly prepared for this.
The best POV to make the Mongol Khaanate this large (note that Khaan is the Mongolian term for "Great Khan" which is the overarch of all Khanates, being the separate Kingdoms) and relatively stable is to take Jochi out of the running.
Borte Khatun, Chinggis'* wife (married much prior to any conquest) was kidnapped by the Merkid tribe. When Temujin (Chinggis' given name) rescued her, their first child was born significantly shy of the nine month gestation period, giving rise to the rumors that Jochi was a Merkid bastard produced by Chinggis' enemies forcing themselves on her.
Of course, Chinggis refused to acknowledge these rumors until the khuriltai where he tried to divide the Khaanate among his sons. Jochi and Chagatai fought over the right to be Khaan (Great Khan), while it was already decided that the four separate Khanates (Golden Horde, Ilkhanate, Moghulistan, and China) would be divided evenly between his four sons. This wasn't enough and Chagatai demanded to be made Khaan since his brother was really a Merkid bastard. Finally, they reached a compromise: their third brother Ogodei would be named Khaan in place of either Jochi or Chagatai.
This conflict resonated later in life when Chinggis' grandsons declared Jochi's line illegitimate rulers of the Golden Horde. During Khubilai's reign in the Yuan Dynasty, the Mongol Khaanate was indeed separate, but it's important to note that the Khaanate was intimately connected economically. The Ilkhans held possessions in China, and Khubilai owned farms and factories in Persia. This pattern repeated throughout the Empire.
The Khaanate united the Silk Route, built it into the Silk Road as they passed their armies through the area, and were able to learn from the cultures they passed through to form new and effective strategies of war and political domination. Ex. though the Mongols had no engineers or siege weapons of their own, when they conquered the Jurched, they adopted the Chinese engineers into their army and effectively learned how to use mangonels, trebuchets, and catapults. Instead of pulling siege engines across thousands of miles of terrain, they built an engineer corps that became a permanent addition to their highly mobile military. The key to Mongol power is economic prosperity and security coupled with cross-cultural advantages. The Chinese didn't mind the extremely foreign and strange Mongol Forbidden City at the center of their empire or the degradation of their Confucian officials (once the highest office of the Realm, they became lower than prostitutes) because they enjoyed new crops, a plethora of horses (an extremely valuable commodity in China) and the advantages of Arab and Greek medicine coupled with their own.
When the Black Death hit, the prime social effect was xenophobia. Everyone from every culture suddenly became afraid of foreigners, and the Mongols foremost. In China, the Mongols solidified their alliance with the Tibetans which pushed the Chinese to hate them. Since the economics links with the world were severed, the subject populations of the different Khanates no longer had any incentive to allow the Mongols to rule them and overthrew the various Mongol khanates.
So your POD should be: Jochi dies heirless on a campaign. With Jochi out of the picture, Chagatai can unopposedly inherit the position of Khaan (by khuriltai of course). This allows long-term stability without the constant fighting over Jochi's bastard heritage.
Next, the Mongols never captured India (or South-Western Europe) because they lacked a tactical advantage: their bows were adapted to the dry, arid steppe and lost accuracy and strength when entering the humid environment of the subcontinent or the Mediterranean**. This disadvantage could (and would) weaken as time went on and the Mongols had time to adapt.
Tolui's grandsons would go on to be the most powerful Mongols after Chinggis himself. So after Jochi's line is extinguished, Chaghatai is made Khaan, and Tolui is made Khan of the Mongol homelands (as befits the youngest Mongol son), Khubilai should inherit. It was truly his genius that made the Yuan Dynasty one of the most powerful and culturally significant regions in history.
That said, (definitely read up on Khubilai, if any Mongol at all) Khubilai tried to make himself Khaan, but it erupted in a short lived Mongol civil war that ended with no Khaan at all. But if Khubilai, without cousins or other rivals, could make himself Khaan and extend his genius from Korea to Hungary, then you're really in the clear.
The invasion of Japan is rather simple: change the landing date (easily enough with butterflies) so the Mongols don't suffer the catastrophic defeat at the hand of mother nature. Otherwise, the mounted modern army of the Mongols easily defeat the individual samurai.
As long as the Mongols stay in the highlands of Europe, their OTL technology works fine. Initially, their main European goal was the grasslands of Hungary where their horses could easily feast and maintain a powerful base with which to attack any other European country. With time, you could have the Mongols gradually encroach into Italy and eventually gain control over the Papacy. The Mongols had a strong Christian population and the election of a Mongol Pope would not be out of the question.
I'm not sure about conquering Switzerland, but at least obtaining the loyalty of some cantons and duchies wouldn't be crazy. And the highlands around the Alps would serve as a better base with which to conquer the rest of Europe. France, Germany, even Spain could fall easily to the Mongols as they moved in and adapted indigenous strategies and necessities to their already powerful arsenal.
I would also outlaw slavery in the Mongol Khaanate. This isn't totally out of the question. Chinggis himself served as a slave when he was young and was sympathetic to the plight of the lower class, especially the slave. Whether there was a deemphasis on slavery and a later reemergence, I can't say. But it's pretty clear that the captured slavic children (which is where we actually get the modern term "slave" from) were sold by the Mongols to Italian business men. The Mongols allowed the Italians to build slaving outposts on the shores of the Black Sea. All those children from the initial Russian/Hungarian campaign were then sold in Egypt. Those same children became some of the first child soldiers and would actually go on to meet the Mongol armies at ain-Jalut.
Even though butterflies would prevent ain-Jalut from happening, and I'm remiss to discredit the efforts of the Arabs and other Muslims of the region, logic goes to show that even if that showdown happened, without the motivations of those slaves fighting against the Mongols, their chances for victory lessen (also the lack of Khanate infighting which allowed the OTL Battle of ain-Jalut to happen). After defeating Egypt, there's no significant state to stop the Mongols from expanding across North Africa and meet up with the European Khanate in Spain.
As for the divisions, after Khubilai Khan's death, I can't say for certain how many divisions would erupt from this mega empire, but it probably depends on how many children Khubilai has. The youngest son always gets the region near the capital (as a sign to take care of the home, hearth, and parents) while the other sons are given the regions of the Empire. Japan would be markedly different from China, so that would probably be its own Khanate. Tibet, while a part of the Yuan Dynasty, was not a province or ruled directly under any Chinese official (either way it wouldn't be a part of Moghulistan). Making the leap by having Chagatai's descendents maintain their rule of Central Asia and move on to conquer India (as they did IOTL) wouldn't be crazy either. It was Badur's goal IOTL, but I predict that in this scenario, they eventually get split into a Central Asian Khanate and an Indian Khanate.
The Middle East would probably still be run by the Ilkhanate, which would now stretch from Persia to North Africa. One of the unintended effects of the Ilkhanate was that it demolished Arab hegemony of Muslim lands. So all the Muslim minority ethnicities would be all too happy to pay homage to the Khanate since the Mongols not only allow religious freedom (destroyed the jizya tax) but also allowed ethnic freedom: all people were equal under the Great Blue Sky.
Europe, I'm not sure. My best guess is that it would be one entire Golden Horde with sub-Khans subservient to the Golden Khan, who would be subservient to the Khaan. It's impossible to maintain an empire that big for too long (though an invasion of Europe, a la the invasion of Japan would be awesome) so infighting would eventually divide the European Khanate into several smaller khanates that would fight each other.
IOTL, Turkic armies helped the Golden Khan maintain control over the Russians. The Khans then converted to Islam which only steeled the Russian resolve. So you'd have to figure which armies the European Khans would depend on to maintain their rule. It'd be a collection of Muslim armies, Christian armies, and probably Mongols too (who were themselves a conglomeration of shamans, Buddhists, Christians, and Muslims). So the Golden Horde, now far more integrated into the larger Khaanate, would maintain its Mongol roots. Britain, France, Spain, Italy, and Germany would fall into chaos for a while as armies of different faiths ravaged the lands. It'd be interesting to see if, say, a German-based Khan converts (fully) to Catholicism and named himself Holy Roman Emperor. I'd put my money on that one coming out on top, naming his own Anti-Pope, and eventually marching an army to Rome (controlled by a Muslim army and a Muslim puppet-Pope) where he then names a "Third Rome." This new Third Rome/German Khanate/Holy Roman Empire could possibly stretch from Poland to Spain. About that time, a Black Death would hit, and have no doubt, it will hit.
Economic integration is key to making the OTL Mongol Empire. This scenario doesn't posit a stronger economic integration, but a larger one. So the Black Death will hit with just as equivalent strength as OTL. The only thing I can imagine making a difference is when these Mongol civil wars take place. If after the Death, then they might kill harder and faster since the infrastructure will be gone and chaos will already reign. If before, it might give the infrastructure time to respond which may put off the civil wars for a generation or so.
tl;dr: Kill Jochi (Borte' bastard, firstborn son, that Chinggis raised as his own) before he can have any heirs. Hand uncontested Great Khan rule to Khubilai (via khuriltai) which extends his genius from Japan to Poland (and possibly Western Europe). Also, outlawing slavery helps.
*"Chinggis" is the more accurate pronunciation of "Genghis." "Genghis" coming from the transliterated Persian spelling, solidified by Chaucer's "Cambyuskan." The Mongolian "ch" is a lot like the Irish, German, or Scottish "ch" as in "loch." So the term "Genghis" isn't pronounced "GGenGGis" but somewhere between "Shinggis" and "Chinggis."
**Though incredibly humid, the capture of Song China had little to do with the Mongol bows. Khubilai captured Song China by building alliances with native Chinese that opposed the Song. The Mongols were incredibly liberal (by even many modern standards) and allowed protection under all people that submitted to their rule. By contrast, the Song were essentially dictators. After the capture of Tibet and the Jurched, many Song citizens just defected to the Mongol lines and brought their native weaponry.
