1690s, a condensed form of some exclamation, usually said to be God's hooks (nails of Christ's Cross) or even God's hocks. Compare godsookers (1670s). The use of Gad for God (as in egad) is first attested 1590s. Among other similar "phraseological combinations" noted by OED (all from 17c.) were gadsbobs, gadslid, gadsniggers, gadsbudlikins, and gadsnouns; in all of which the second elements are sometimes said to be mere fanciful syllables.
Others are reading
<a href="https://www.etymonline.com/word/egad">Etymology of egad by etymonline</a>
Harper, D. (n.d.). Etymology of egad. Online Etymology Dictionary. Retrieved $(datetime), from https://www.etymonline.com/word/egad