There are two pieces of the puzzle here: First Hell, and Second, Satan. The question is when were these two pieces first merged together. Technically speaking, the Bible never explicitly links these two. Despite this, there is an impression - even in Jesus teachings - that the most evil creature ruled over the underworld in all religions back to the earliest known records - including Christianity.
In Canonical Biblical writings, the concept of the underworld (שְׁאוֹל; Sheol) first appears in Genesis 37:35
All his sons and daughters stood by him to console him, but he refused to be consoled. "No," he said, "I will go to the grave [שְׁאוֹל; Sheol] mourning my son." So Joseph's father wept for him.
And in Job 26:6, this place is regarded as either being or containing a place of destruction.
The underworld is naked before God; the place of destruction lies uncovered.
Much like in Christianity, where some believe judgement is not immediate and the soul exists in an intermediate state before the Resurrection and the Millenial Kingdom, the same is true of some Jewish schools of thought where souls are though to dwell in שְׁאוֹל (Sheol) until "Olam Ha-Ba" (the world to come) at which point there will be a bodily resurrection of the dead.
Similarly, where some in Christianity believe judgement is immediate and the righteous go to Heaven to dwell with God before the final judgement at the end times in Revelation, some schools of Jewish thought believe that the righteous go to Gan Eden upon death. Where Christians most often believe that the unrighteous go to Hell upon death, some according to Jewish thought go to Ghenna/Gehinom. Depending on the viewpoint, this may be an eternal punishment, or may only be punishment for a time, similar to the Catholic doctrine of Purgatory.
In any event, Luke 16:19-31 paints a pretty vivid picture of Hell being a place of torment.
The word Satan derives from the Hebrew word שׂטן for "accuser" or "Adversary" used in Job to describe the character that many regard as Satan. The Hebrew and Aramaic Lexicon of the Old Testament defines this word as,
1 accuser, adversary: a) human: 1K 5:18; b) mal˒ak yhwh + Nu 22:22, 32; — 2. spec. supernatural figure: haśśāṭān, the Satan + Zc 3:1f Jb 1:6–2:7 (14 ×); > śāṭān (proper name) + 1C 21:1
Modern Judaism does not regard Satan as being malevolent or inherently evil, but instead simply being a servant of God to ensure that mankind has free will.
Appearing alongside the entry for HaSatan in the HALOT is this entry however,
qal: impf. יִשְׂטְנוּנִי; inf. שִׂטְנוֹ; pt. pl. cs. שׂטְנֵי, sf. שׂטְנַי: bear a grudge against, harbor animosity toward Ps 38:21.
Accordingly, Christianity regards Satan as malevolence and the epitome of evil because if God is truly good, then the opponent and adversary must be opposed to that good - therefore evil.
Judiasm around the time of Jesus also paints this picture with books like 1 Enoch painting Satan as a evil, malevolent fallen angel.
Mark Edward and I were also able to trace the link between Satan and the Serpent in the Levant all the way back to the earliest Egyptian inscriptions. Genesis appears to have been written with the understanding that ancient readers would be comparing the Genesis creation account to Egyptian and Babylonian creation accounts.
Nearly all of the creative stories in the ancient Middle East had a strong serpent motif with serpents representing evil. This is especially pronounced in Egyptian and Greco-Roman mythology with the serpent Apep ruling the underworld - a place of chaotic torment in Egyptian mythology. Every day, Apep was thought to torment Ra as he traveled through the underworld. By inviting a comparison to these myths, the Bible (Genesis) is essentially equating and implying that the serpent and Satan are an evil tormentor who rules the underworld.
In Egyptian, Greco-Roman and most other mythology, the god who ruled over the underworld was typically the embodiment of evil - usually one of the more evil if not the most evil god in the pantheons. Wikipedia states,
Gehenna was initially where apostate Israelites and followers of various Ba'als and other Canaanite gods, including Moloch (or Molech), sacrificed their children by fire (2 Chr. 28:3, 33:6). Thereafter it was deemed to be cursed (Jer. 7:31, 19:2-6)
Yahweh is a powerful God. Therefore, anyone capable of standing in opposition to Him must also be powerful. As Gehenna is the destination of evil, it is only natural to assume that that power would allow the adversary to rule over Gehenna (hell). When we remember that all of the other creation stories had the token malevolent god ruling over the underworld and realm of the dead, it is easy to see how the belief that the adversary was ruler of the place of torment and that the adversary was the primary tormentor himself (as lord of that realm) came to be.
Therefore, while there may not be an explicit Biblical basis for this idea, the idea is certainly implicit to the text and the traditions surrounding it. Furthermore, the origin of this belief can be traced to the earliest known records of any religion.