So, first. Majus is the Arabic equivalent of the word "Magus"; it must have come into Arabic through some intermediary (probably Aramaic) from Old Persian, since the -us stem disappears already in Middle Persian; the dual in New Persian is "Mogh" which means "[ancient] Zoroastrian priest".

More to the point, I had a look around, and the best source I found was a doctoral disseratation "'Ifranjalism': The [European] Other in Medieval Arabic Literature and Culture, 9th to 12th century (A.D.)" by Nizar F. Hermes.

Hermes notes,

As demonstrated by al-Hajj, one of the leading scholars in Andalusian/western relations, medieval [Andalusian] Muslims used "majus", the same word their eastern co-religionists used primarily in referring to Persian Zoroastrians, to describe all northern non-Christian Europeans who used fire frequently in their rituals.

Another source, an article "The Vikings in Arabic Sources" by A. Tibi, notes

The Andalusians called [Vikings] majus ... because they were heathens who cremated their dead.

This is plausible enough, but one thing nags me: Cremation is a heinous sin in traditional Zoroastrianism, because the ashes of a corpse are thought to be nasu, dead matter, which is extremely ritually impure, and because it taints the purity of the flame. Another line in the aforementioned thesis mentions:

Of historical importance is al-Ghazal's indication that the Christianized vikings used to attack and enslave the vikings who chose to keep their old faith (fire-worship) what al-Ghazal has described as "heinous practices" mainly in reference to incestuous marriages between brothers and sisters.

If the vikings did indeed practice incestuous marriages between full siblings, that would be another good reason to make a connection to Zoroastrians; the author notes that this may indeed be al-Ghazal's intention in mentioning incestuous unions.

Notably, he points out that ibn-Fadlan and in general Eastern Muslims did not use the term majus (ibn Fadlan uses the term Rusisiyya). This is especially interesting considering ibn Fadlan actually describes a cremation, which would suggest the cremation-Zoroastrianism connection, if one was made, would be out of ignorance of Zoroastrian practices as one would be likely to encounter in Andalusia.

That's about the best I can do. I don't think there is any primary source stating explicitly why they refer to them this way, so it's all informed speculation in the end.