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 first recorded 1855, from French sauce tartare.