This is what I've read, but I'm not sure how much of it is fiction or truth:
The Tatars were a Turkic (?) tribe on the western border of Mongolia that had been subjugated by the Mongols. Consequently, they provided a large contigent of forces which the Mongols used primarily in the invasions of Central Asia, Eastern Europe, and West Asia. In other words, the majority of the troops used by the Mongols in those areas would actually have been Tatars, while a smaller core of "true" Mongols maintained command. Therefore, the Europeans would probably have known the invaders as "Tatars," which they re-interpreted as "Tartars," or people from Tartarus.
Or something like that.