The Mongols swept across Eurasia from China to Hungary, defeating all armies, looting cities, taking slaves, and exacting tribute. Rus lands were devastated except in the north, where Novgorod submitted before the Mongols reached the city. In Rus lands and Europe, the Mongols were also called Tatars or Tartars, and Mongol overlordship of Rus was called the Tatar Yoke. (The painting depicts the Battle of Legnica in Poland but is illustrative of the Mongols' ferocity in Rus lands.)
The northern Asian steppes had many semi-nomadic, horse-riding ethnic groups, often organized in tribes and confederations of tribes and often being conquered by mostly-short-lived horse empires of other tribes and confederations. The Mongols were one of many groups here, and their turn at empire came in the 13th Century under their khan, Temüjin, who assumed the title Genghis Khan ("Universal Ruler").
As the Mongols conquered nearby groups, they integrated them into their empire and armies. This included the Tatars, a confederation of Turkic-speaking tribes. Most of the soldiers in the Mongol armies that swept west into Kievan Rus, Poland, and Hungary were actually Tatars, under Mongol leadership. Thus, the Rus and eastern Europeans typically encountered Tatars, not Mongols, hence calling their conquerors Tatars.
Europe was mostly Christian. Christians believed in Hell, and at least for some Tartarus was a part of Hell. However, in the Middle Ages, many Christians believed that places like Eden and Tartarus had actual, albeit uncertain, locations on Earth. Tartarus was believed to be somewhere far to the east in Asia. Christian revelation also foretold that Satan would "deceive the nations which are in the four corners of the earth, Gog and Magog, to gather them together to the war". The Mongol invasions and conquests with their immense death toll and brutality seemed to some Christians as Satan's invasion. They confused the Mongol's Tatar soldiers with Tartarus, calling them Tartars. They soon began using "Tartary" as the name for the Asian region east of the Caspian Sea and north of China.