How did Paul know so much about Melchizedek? 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.