「[蓬萊]{Hōrai}」is actually the wholesale assignment of the name of a Chinese mythological location to a superficially similar but quite distinct Japanese legend. It may otherwise be called「蓬萊山」(lit. Mount Hōrai) or abbreviated as「蓬山」; this name is due to the Chinese legendary location being a mountain hosting the Eight Immortals.
Some of its earliest appearances in Japanese literature include Nihon Shoki and the lost work 『[丹後國風土記]{Tango no kuni fudoki}』, a Fudoki on Tango Province written during the Nara Period. Quote from the opening text of Tango no kuni fudoki:
與謝郡。
日置里。
此里有筒川村。此人夫,日下部首等先祖,名云筒川嶼子。為人,姿容秀美,風流無{{ko:類}}。斯,所謂水江浦嶼子者也。是,舊宰伊預部馬養連,所記無相乖。故,略陳所由之旨。
長谷朝倉宮御宇雄略天皇御世,嶼子獨乘小船,汎出{{ko:海}}中為釣。經三日三夜,不得一魚,乃得五色龜。心思奇異,置于船中即寐,忽為婦人。其容美麗,更不可比。
嶼子問曰:「人宅遙遠,{{ko:海}}庭人乏,詎人忽來?」女娘微咲對曰:「風流之士,獨汎蒼{{ko:海}}。不勝近談,就風雲來。」嶼子復問曰:「風雲何處來?」女娘答曰:「天上仙家之人也。請君勿疑。垂相談之愛。」爰嶼子知神女,鎮懼疑心。女娘語曰:「賤妾之意,共天地畢,俱日月極。但君奈何,早先許不之意。」嶼子答曰:「更無所言,何懈乎?」女娘曰:「君宜迴棹,赴于蓬山。」嶼子從往。
(My own translation given below.)
Yosa District.
Township of Hioki.
There was a village named Tsutsukawa. A man named Tsutsukawa no Shimako lived here, who was the ancestor of the chiefs of the Kusakabe Clan. He was peerless in his grace and elegance. Thus, he was known as Mizunoe no Urashimako. The contents of this record are the same given as that by the official Iyobe no Umakai, and it is declared that this is a summary.
During the Reign of Emperor Yūryaku, one day Shimako boarded a small boat alone and drifted out to sea to do some fishing. After three days and three nights passed, he did not catch one fish, but finally caught a five-coloured turtle. He thought this was very peculiar, and took the turtle in his boat and went to go to bed, when suddenly it turned into a woman, whose beauty was second to none.
Shimako asked the woman in surprise: "This place is far from the homes of people, and there is no-one out on the sea. How did you suddenly appear?" The young lady smiled, replying: "A graceful and elegant man, drifting alone out in the blue sea. I could not see this and resist approaching and talking to you, and rode the wind and clouds to come." Shimako replied, asking: " Where did the wind and clouds come from?" The lady replied: "From the immortal people in heaven. Please don't be suspicious. Let's talk and love together." After Shimako found out that the lady was a goddess, his suspicions were gone. The lady spoke: "I want to pledge myself to you, from heaven to earth, until the end of time. What are your thoughts about this?" Shimako replied: "I have nothing to add; do you have any reservations?" The lady replied: "Turn the boat around, and let us journey to 蓬山." Shimako complied.
By most interpretations,「蓬山」is supposed to be read as「[常世の國]{Tokoyo no Kuni}」, which is a realm in Traditional Japanese mythology of everlasting life somewhere out in the distant sea. In the majority of records to do with specifically Japanese mythology, the name or characters「蓬山」(and similarly「蓬萊」,「蓬萊山」) are borrowed for this purpose due to their superficially similar idea to the Chinese Penglai, but there isn't an actual mythological connection between Penglai and Hōrai.
The superficial connection can be seen if one reads the texts behind Chinese Penglai. Quote from the Classic of Mountains and Seas, a mythological geography account of pre-Qin China:
蓬萊山在{{ko:海}}中郭曰上有仙人宮室皆以金玉爲之鳥獸盡白望之如雲在渤{{ko:海}}中也
Mount Penglai, in the middle of the sea Guo Pu notes: "On the mountain resides Immortals and their palaces are made of gold and jade. The birds and beasts there are completely white. To stare at the mountain is like gazing at clouds. It is located in the middle of the Bohai Sea."
Linguistically, there is a striking similarity between 「蓬萊」(Old Chinese: /*boːŋ rɯː/) and several words for sea/ocean in some Southeast Asian languages (Burmese and Jingpho: panglai, Shan: paaŋ2 laaj2).