From Old Japanese. By one analysis, this may be a compound of 田(ta, “rice paddy”, a common place where cranes can be found) + つ(tsu, “crane? large bird?”). The tsu changes to dzu, modern zu as an instance of rendaku (連濁). This tsu is probably the tsu in tsuru (see below).
Given a crane's long neck and how the bird hunts, possibly related to 蔓(tsuru, “vine”); 弦(tsuru, “bowstring; musical instrument string”); 釣る, 吊る(tsuru, “to hang down; to string up; to fish”). Given how cranes flock together, possibly related also to 連る(tsuru), older root form of modern verb 連れる(tsureru, “to accompany”). That said, 連る also appears to ultimately derive from 蔓(tsuru, “vine”).
Vovin (2008) considers it possibly related to an ancestor of Korean두루미(durumi, “crane”), with a root-final -m vanishing later, leaving only a Kansai accent pattern behind.
The reading tsuru is first seen used to mean a crane(the bird) from the late Heian period. Prior to that time, the only reading used for the bird was tazu. However, the kanji 鶴 was used in the Man'yōshū as a phonetic ateji for the verb ending -tsuru, suggesting that tsuru may have already existed as an everyday term meaning a crane.
^ Bjarke Frellesvig and John Whitman, editors (2008), chapter 7, in Proto-Japanese: Issues and Prospects, Amsterdam; Philadelphia: John Benjamins Publishing Company, Proto-Japanese beyond the accent system, pages 140-156
^ 1998, NHK日本語発音アクセント辞典 (NHK Japanese Pronunciation Accent Dictionary) (in Japanese), Tōkyō: NHK, →ISBN