"tortoise," c. 1600, originally "marine tortoise," from French tortue, tortre (13c.) "turtle, tortoise" (often associated with diabolical beasts), of unknown origin. The English word perhaps is a sailors' mauling of the French one, influenced by the similar sounding turtle (n.2). Later extended to land tortoises; sea-turtle is attested from 1610s.
"turtledove," Old English turtle, dissimilation of Latin turtur "turtledove," a reduplicated form imitative of the bird's coo. Graceful, harmonious and affectionate to its mate, hence a term of endearment in Middle English. Turtle-dove is attested from c. 1300.