The Kumarapala-Bhupala-Charita of Jayasimha Suri provides a legendary genealogy of Mularaja. It states that the mythical progenitor of the Chaulukya dynasty was Chulukya, a great warrior. He established his capital at Madhupadma, and the dynasty came to be known as the Chaulukyas after him. His successors included several kings including Simha-Vikrama and Hari-Vikrama. After 85 descendants of Hari-Vikrama came Rama. Bhata or Sahajarama, the son of Rama, defeated the Shakas. Bhata's son Dadakka defeated the Gaja kings of Pipasa. Dadakka's kingdom occupied by Kanchikavyala, who was succeeded by the king Raji. Mularaja was the son of Raji and his queen Liladevi.
The Vadasma (Varunasarmaka) grant inscription of Mularaja's son Chamundaraja states that Mularaja was a descendant of one Vyalakanchi-Prabhu. This Vyalakanchi is probably same as the Kanchikavyala mentioned by Jayasimha Suri. Based on this, historian Asoke Majumdar believes that Suri's legendary account seems to be at least partially accurate: Rama and his successors appear to be historical figures. It is possible that they were small princes of a place called Madhupadma. V. V. Mirashi speculated that this place might have been situated on the banks of the river Madhuveni (present-day Mahuwar), which is a tributary of Betwa. Majumdar, on the other hand, identifies it with modern Mathura.
The 14th century chronicler Merutunga states that Mularaja was so named, because he was born under the auspices of the Mula nakshatra. According to this legend, Raji (or Raja), Bija and Dandaka (or Dadakka) were three brothers. Raji's knowledge of horse-riding greatly impressed Samanta-simha, the Chapotkata (Chavda) king of Anahilapataka. He became a close friend of the king, and married Liladevi, the king's sister. Liladevi died while she was pregnant; her womb was cut open and the infant Mularaja was taken out.
Three other chroniclers — Arisimha, Udayaprabha and Krishnaji — also describe Mularaja as the son of sister of the last Chapotkata ruler.