The Old Testament has 3 verses on the subject. 2 in Genesis 14:18 and 19 and Psalms 110:14. That's all. Yet Paul has given a surprising description of Melchizedek, the complete chapter of Hebrews 7 is devoted to the subject.
The writer of Hebrews approached the subject of Melchizedek through a combination of different avenues.
1) What’s listed explicitly in the text, through both direct information from scripture (the King of Salem/Peace), and through translation of his name (King of Righteousness).
2) The way Melchizedek acted, playing the part of a priest by blessing God’s people.
3) The way Melchizedek was treated, Abraham giving him a tithe indicating his superiority to Abraham.
4) The reference to the “Priestly Order of Melchizedek” in the Psalms.
Taking the above into account, The writer of Hebrews is anticipating the objection to Jesus’ priesthood on the grounds of Him being from the line of Judah, not Levi. The writer is pointing to this “other order” that wasn’t from the line of Levi (because Levi was from Abraham, and Melchizedek is clearly outside of the line of Abraham).
The author develops this point further by both literary reference and literary license. Because the character of Melchizedek just appeared and disappeared in the Torah, it’s “as if” he didn’t have a beginning or end, “as if” his priestly order has always been. Because Abraham tithed to Melchizedek and was blessed, and because the superior always blesses the inferior, then logically the priestly order of Melchizedek must be greater than the priestly order of Levi (Melchizedek > Abraham > Levi).
The writer of Hebrews didn’t have any special knowledge of Melchizedek, he just expounded on the available information as the Holy Spirit led him, both through his own understanding and the clear messianic nature of Psalm 110, which is referring to Jesus the Messiah.
Paul knew because of Jewish Tradition, Guided by the Holy Spirit, he understood that the traditions where not traditions of men, but traditions of God.
The Targum, the Aramaic interpretive translations, identify Malchizedek as the Son of Noah, Shem. The Targum, or Targumim, is part of the traditions used by the Rabbi's to identify and explain the Hebrew Scriptures to an audience that spoke mainly Aramaic after the Babylonian Captivity. The oral tradition as well as other traditions such as actions like the Jewish Liturgy, was how the Rabbi's preserved their teaching. It is through these traditions that we get the names of Jannes and Jambres which are not mentioned in the OLD Testament which Paul uses without question identifying these men in scripture. Much like what is done in the Current Church started by Christ, the actions of the faithful, repeated constantly over and over again to preserve the Traditions of God, are what maintain the orthodoxy of the Faith.
In Short, it was the traditions of the Rabbi's which held that Shem was the Descendant of Noah and Grandfather of Abraham. Who, at the instruction of God, offered Bread and Wine as a Sacrifice to God. This foreshadowed Exodus 24, where Moses, the Priests, and 70 Elders ate and Drank as they beheld God. What did they eat and drink, the answer can be found by the Table of the Presence, the food that was made present, The Showbread, placed on the Table of the Presence in the temple and with it flagons for Libation offerings, flagons for pouring out wine.
These Holy and Sacred Traditions of God continued to the Passover meal in the upper room, where the Jews after the Roman occupation started another tradition to preserve their Culture as Gods People. In fear of losing their identity the started the tradition of the Passover Seder, which Christ fallowed and altered in the upper room as the long awaited Messiah was himself and instead of opening the door to wait for the messiah as the Jews do even today, he walked through that door to inevitably,Calvary. Christ, having foreknowledge of the persecutions that would be on his Church, instituted a Sacred Tradition of his own, that we would do continually, the Holy Eucharist, Himself being the Bread and the Wine that was poured. This is in reality what the New Covenant is, the Eucharistic Meal, Christ offering himself to us, drawing us to him. Paul knew this, he knew the importance of this Bread and Wine offering only too well.