Sadhguru's background seems to be based on various Shaivite sects across Yoga and Tantra. In my answer, I am not confirming Sadhguru's view (version of AdiYogi) exactly as he tells, but only providing some scriptural basis where Shiva has been considered First or Supreme Yogi with some details matching Sadhguru's version.
Tirumantiram, by Tamil Siddha/Yogi/Tantric Tirumular, talks about Shiva as Supreme/Primordial Yogi. The text is divided into various Tantric sections. In verses 337 and 338 of Tantra Two, Rishi Agastya is mentioned to be one of the first disciples of Supreme Yogi Shiva, who brought down some of the teachings of Shiva from the North of the Himalayas to South India. This again coincides with Sadhguru's version of Shiva asking the Saptarishis to spread Yoga to different parts of the world and asking Rishi Agastya to come to the South of India. The text further states that Rishi Agastya later also became a companion and Guru of Tirumular himself and helped him grow in Yoga. In Sadhguru's version of the AdiYogi Story, Rishi Agastya is one of the seven sages that learn Yoga from Shiva. So, at the very least, this aspect of Sadhguru's story matches what Tirumular states.
As you mentioned, in Nath Yogi tradition, Shiva is considered as AdiNath (First Nath) or AdiGuru (First Guru), which is synonymous with AdiYogi (First Yogi), given that Nath Yogi tradition emphasizes more on the practical application of Hatha Kundalini Yoga rather than an intellectual discussion on metaphysics.
In Dattatreya Yoga Shastra, there is the following conversation between Dattatreya and Samkrti that also states that Shiva teaches esoteric techniques to Parvati and some "leaders of his troop" (maybe a small number of sages?) at Srikantha (a mountain of the Garhwal Himalaya in Uttarakhand India) and other places. The conversation -->
Dattatreya: "The Yoga of Dissolution (layayoga) happens as a result of the dissolution of the mind by means of esoteric techniques (samketas). Ādinātha has taught eighty million esoteric techniques."
Sāmkrti said: "Please tell me, what form does Lord Ādinātha take? Who is he?"
Dattātreya said: "The names of Mahādeva, the great god, are Ādinātha, Bhairava, and Lord of the Śabaras. While that mighty god was sporting playfully with Pārvatī in the company of the leaders of his troop in [various places such as] Mount Śrīkantha, Śrīparvata, the top of a mountain in the region of the Banana Forest, [and] the mountain at Citrakūta covered with beautiful trees, he, Śankara, out of compassion, secretly told an esoteric technique to each of them in those places. I, however, cannot teach all of them in detail. I shall gladly proclaim some of them..."
In Vijnana Bhairava Tantra, Shiva/Bhairava is also considered as Supreme (First and Foremost) Yogi to teach Shakti/Bhairavi 112 ways to attain liberation. This matches the aspect of Sadhguru's version where AdiYogi taught 112 ways to liberation.
Shiva is also known as Primordial Yogi Shiva in a few other Indian texts and traditions like [Shiva Samhita, e.g. translation by Mallinson; Varenne, p. 82; Marchand for Jnana Yoga].
Here is a link to the website of a very real Himalayan Yogi known as MahaSiddha IshaPutra, the Peeth of Kaulantak lineage. He and his lineage have no relation to Sadhguru. They also consider Shiva to be the First and Supreme Yogi who provided Yoga to the rest of the world. Link
Tantric Tibetan Buddhism (which is very different from Gautama Buddha's Theravada Buddhism) has a famous text called "Kalachakra Tantra." Tantric Buddhism has more in common with Shaivite-Shakta Tantra traditions than with other branches of Buddhism. In that text, "Maha Kala" (a famous fierce form of Shiva) is considered to be the supreme force and provider of Yoga. However, they do not equate Maha Kala with Shiva. They equate Maha Kala with "AdiBuddha" (First Buddha/Primordial Buddha), a blue-colored fierce Yogi with a Shakti-like consort. AdiBuddha matches Shiva more than Gautama Buddha. This makes some think that they are trying to convert "Shiva" into "Buddha" to fit him into the Buddhist framework. This is also one of the many reasons why Theravada Buddhists consider Tantric Buddhists as heretics.
I will be quoting the following points from Nishantha Ulhas Nair's answer to the same question posted on Quora Link: Quora Link
- "Adiyogi Shiva appeared over 15,000 years ago?
The Vedic period is considered to be around 1500–600 BCE, around the time of the composition of the four sacred Vedic texts (Rigveda, Yajurveda, Samaveda, and Atharvaveda). And we have evidence that Shiva worship and yoga predates this period. The Pashupati seal (dated around 2350-2000 BC), discovered in the Indus Valley Civilization (IVC; a pre-Vedic period) shows the figure of yogi sitting in the yogic lotus posture. This figures is considered to be Shiva by many scholars. John Marshall gives the following reasons why he considers this figure to be Shiva: "My reasons for the identification are four. In the first place the figure has three faces and that Siva was portrayed with three as well as with more usual five faces, there are abundant examples to prove. Secondly, the head is crowned with the horns of a bull and the trisula are characteristic emblems of Siva. Thirdly, the figure is in a typical yoga attitude, and Siva was and still is, regarded as a mahayogi—the prince of Yogis. Fourthly, he is surrounded by animals, and Siva is par excellence the "Lord of Animals" (Pasupati)—of the wild animals of the jungle, according to the Vedic meaning of the word pasu, no less than that of domesticated cattle." There are also other similar seals of Shiva found in the IVC. There is also Shivalingas found in IVC (3500 BCE to 2300 BCE). Mother Goddess worship was also prominent in IVC. There is no evidence of Sanskrit or Vedas having existed in the IVC, as the Indus valley script has nothing to do with Sanskrit. Dhyansky (1987) discusses about yoga existing in the Indus Valley Civilization. Harappa, which is one of the sites when IVC excavations were found and whose name comes from the nearby village, can be split into "Hara" (another name for Shiva) and "appa" (meaning father in some South Indian languages) [book: Tantra, its mystic and scientific basis]. Also, some scholars have said that prehistoric paintings at the [Bhimbetka rock shelters (dated pre-10,000 BCE period) shows figures of Shiva dancing, Shiva's trident, and his mount Nandi. These are good evidences showing that both yoga and Shiva worship existed in the pre-Vedic period. So when Sadhguru says Adiyogi Shiva appeared over 15,000 years ago, I think he is referring to an approximate time, in the pre-10,000 BCE period." -- Nishantha Ulhas Nair
One can also watch the "The History of Yoga" documentary mentioned in Sanatana Dhara's answer to see the existence of Yoga and Shiva worship in the pre-Vedic period.
- "Shiva, also known as Dakshinamurthy (one who is facing south), is seen traditionally as the first guru (Adi Guru), who taught Yoga, tantra, music, arts, shastras, etc. Dakshinamurthy is known to have taught a few sages. Sadhguru's representation of Shiva as the south-facing Adiyogi is a representation of Dakshinamurthy. The traditional Guru pooja also shows gratitude to Shiva." - Nishantha Ulhas Nair
Summary: Looking at all these points, at the very least, we can conclude that Sadhguru did not create his view/theory out of thin air. The idea of Shiva being "AdiGuru/AdiNath/AdiYogi/Abode of Yoga/Supreme Yogi" has existed since the earliest roots of formal Sanatana Culture. Even if Sadhguru's version of AdiYogi might not be true exactly as he tells, some aspects of Sadhguru's version of AdiYogi do perfectly match aspects mentioned in various Yogic/Tantric scriptures.