old alternative form of khan (q.v.), 1550s, from French cham, Medieval Latin cham, alternative forms of chan, can. "Formerly commonly applied to the rulers of the Tatars and Mongols; and to the emperor of China" [OED]. Used figuratively of any great leader in any activity or art.
The natives were believed by the Europeans to be anthropophagites. Columbus, seeking evidence that he was in Asia, thought the name meant the natives were subjects of the Great Khan. The form was reinforced by later writers who connected it to Latin canis "dog," in reference to their supposed voracity, a coincidence which "naturally tickled the etymological fancy of the 16th c." [OED]. The Spanish word had reached French by 1515. Used of animals from 1796. An Old English word for "cannibal" was selfæta.
mid-14c. (implied in Tartary, "the land of the Tartars"), from Medieval Latin Tartarus, from Persian Tatar, first used 13c. in reference to the hordes of Ghengis Khan (1202-1227), said to be ultimately from Tata, a name of the Mongols for themselves. Form in European languages probably influenced by Latin Tartarus "hell" (e.g. letter of St. Louis of France, 1270: "In the present danger of the Tartars either we shall push them back into the Tartarus whence they are come, or they will bring us all into heaven").
The historical word for what now are called in ethnological works Tatars. A Turkic people, their native region was east of the Caspian Sea. Ghengis' horde was a mix of Tatars, Mongols, Turks, etc. Used figuratively for "savage, rough, irascible person" (1660s). To catch a Tartar "get hold of what cannot be controlled" is recorded from 1660s; original sense not preserved, but probably from some military story similar to the old battlefield joke:
Irish soldier (shouting from within the brush): I've captured one of the enemy.
Captain: Excellent! Bring him here.
Soldier: He won't come.
Captain: Well, then, you come here.
Soldier: I would, but he won't let me.
Among the adjectival forms that have been used are Tartarian (16c.), Tartarous (Ben Jonson), Tartarean (17c.); Byron's Tartarly (1821) is a nonce-word (but a good one). Tartar sauce is attested by 1855, from French sauce tartare.