The story is recorded in two letters preserved in Vatican's library, first in De Facto Ungarie Magne, a Fratre Riccardo Invento Tempore Domini Gregorii Pape Noni (Regarding the matters of Greater Hungary, by Father Riccardus in the time of Pope Gregory IX) by a certain Richardus, thought to be some kind of superior of Julian, the second was written by Julian himself, the second written by Julian hismelf and sent to Vatican, titled Letter on the life of Tatars (I couldn't find original Latin title).

To put it into context, this is the time that Europe starts hearing about Mongols. There is a very real need for information about them. And this goal was combined by the desire to convert the various peoples of the steppes to Christianity. In 1221 the only 5 year-old Dominican order starts organizing in Hungary to make it a base for eastern missions. By 1228 Bejbars/Bars, Cuman ruler converts and the King of Hungary nominally becomes their suzerain. In 1229 the Diocese of Cumania is set up. In 1232 Friar Otto and his three companions are sent out by King Bela. This mission is today seen as the prelude of Julian's. We know very little of their travel, it's only mentioned in one paragraph of the Riccardus letter, according to it only that only Otto returned and died shortly after, but he told everything he recalled, including meeting with peopel speaking Hungarian. This likely gave impetus to Julians first mission, including finding the lands of old Hungarians.

As far as these accounts go you have to take Julians word for it. But consider some points here, he was a learnt dominician friar, he was on a mission sent by the King, his two travels were both recorded sharde much points. And from his second mission he returnt with a letter from Batu Khan. Finally, Giovanni da Pian del Carpine was sent by Pope Johannes V to the Mongol khan in 1245, and he too reports of a Magna Hungaria ("The long and wonderful voyage of Frier Iohn de Plano Carpini"). If Julian made up the part of talking with these Eastern Hungarians, why did he accept to go out for a second mission, with a letter from Bela for the leaders there? Do recognize that such knowledge also implied the need for further Christian missions to the East. It hardly ups for a friar to lie about his harsh travels (see how Otto's mission ended, or that Julian had to pretend to be an imam for a while) just so he can do it more.