I think the popularity of the phrase "personal relationship with Jesus", and "accepting Jesus into your heart" among evangelicals comes from the influence of a few evangelical figureheads in the past century such as Billy Graham, Bill Bright, and others.
However, the concepts themselves - when understood correctly - can certainly be found in very explicit terms within Scripture.
1) "A Personal Relationship with Jesus" - In speaking to this phrase let me first say what I believe the intent behind the phrase is, when most commonly used: The idea of a "personal relationship with Jesus" speaks primarily to the idea that a person does not just know about the historical character called Jesus the Christ in a purely historical or religious context. It speaks to the fact that the Gospel of Jesus Christ is the message that by placing one's trust in Jesus for the forgiveness of their personal sins they can have restored fellowship with God, and a direct relationship with him where God listens to the individual and relates to the individual through the Holy Spirit, through the Scriptures, and through the Body of Christ (the Church).
The phrase speaks to the personal nature of this relationship and how biblical Salvation is a personal process where God interacts individually with each of the people he is giving salvation to - not just in a generic and disconnected relationship to all of mankind.
While we do not read the words as such in the Scriptures, neither do we read any of our English words in the original text - all are an interpretation. But while we don't read these words even in our English interpretation, the concept behind them is very much present in many passages throughout the New Testamant.
So while I would assert that the actual words in question have been made popular by contemporary evangelical leaders (who started the exact linguistic combination of words I surely don't know), I would also argue that the concept which they actually represent is not unique to our culture, or some post-enlightenment thinking. The idea of personal salvation is very explicitly discussed in the Scriptures.
Here's a few of the passages in the New Testament that make the case:
Consider John 14:23-26 which emphasizes the incredibly interpersonal relationship between the person who loves Jesus and God, to the extent where Jesus describes coming and living inside that person:
Jesus replied:
If anyone loves me, they will obey me. Then my Father will love them, and we will come to them and live in them. But anyone who doesn’t love me, won’t obey me. What they have heard me say doesn’t really come from me, but from the Father who sent me.
I have told you these things while I am still with you. But the Holy Spirit will come and help you, because the Father will send the Spirit to take my place. The Spirit will teach you everything and will remind you of what I said while I was with you.
Also, consider Revelation 3:20 which again uses an unmistakably interpersonal analogy:
Listen! I am standing and knocking at your door. If you hear my voice and open the door, I will come in and we will eat together.
In the first century culture of the middle east, eating together was a very personal things. As much as we want to peg the enlightenment with being the source of our individualism (and it certainly was on a certain scale), it's not as though the idea of personal, intimate relationships were absent from society before that time period. In fact, one of the greatest demonstrations of a personal, intimate interaction you could have with another person in ancient culture was to eat a meal with them. It was a symbol of deep inner fellowship. So for Jesus to say "I will come in and we will eat together" is explicitly language of personal intimacy.
So though the words in our present form were not combined as such, the connotation certainly existed in very explicit terms in Scripture.
2) "Accepting Jesus into your heart" - Although you didn't ask about this phrase, it's very commonly used in conjunction with the other, so it's worth mentioning...
Now I don't know that this phrase in the cliche form it has become is particularly helpful in sharing the Gospel with others, but it certainly seems to have biblical basis for it's connotation.
The idea of "accepting Jesus into your heart", or "receiving Christ" comes from the biblical notion of "believing in Jesus," or as some translations say, "receiving him":
But as many as received Him, to them He gave the right to become children of God, to those who believe in His name. (John 1:12)
In the above passage from the Gospel of John, John is presumably referring to people who "reveived" Jesus as the Messiah, or Sent One from God. While many rejected Jesus (particularly the religious leaders), his own followers "accepted" him as God's Messiah.
Further, on a more conceptual level, the "heart" has long been considered by cultures to be a representative term for the "seat of emotion", or "the innermost part" of a person's being, or even the place where a person's love originates.
It also is used to represent a place of "authenticity" or "sincerity." If I say, "I mean it from the bottom of my heart," you know what I'm really trying to say is that I'm being authentic and sincere in the action or words associated with that.
So in this regard "accepting Jesus into your heart" may simply speak to a genuine and sincere belief or trust in Jesus as who is claimed to be, as opposed to an intellectual acknowledgement of his mere historical existence.
Finally, there is another very interesting passage in one epistle where I believe the specific wording about accepting him "into our hearts" may be actually derived from:
...so that Christ may dwell in your hearts through faith; and that you, being rooted and grounded in love, may be able to comprehend with all the [m]saints what is the breadth and length and height and depth, and to know the love of Christ which surpasses knowledge, that you may be filled up to all the fullness of God. (Ephesians 3:17-19)
As a point of commentary: All this being said, I believe both of these phrases when used in the cliche way that most of us have heard them serve little purpose in communicating the real nature of life in Christ. The trouble is that when they are used as a cliche way to tell somebody what it means to be a follower of Jesus, they are often an oversimplification of what the Gospel life is really about. They usually lead to some prayer to "accept Jesus into your heart" which is more akin to an incantation than to actually beginning a real walk with Christ.