According to the most learned among the Scots, if any one desires to learn what I am now going to state, Ireland was a desert, and uninhabited, when the children of Israel crossed the Red Sea, in which, as we read in the Book of the Law, the Egyptians who followed them were drowned. At that period, there lived among this people, with a numerous family, a Scythian of noble birth, who had been banished from his country and did not go to pursue the people of God. The Egyptians who were left, seeing the destruction of the great men of their nation, and fearing lest he should possess himself of their territory, took counsel together, and expelled him. Thus reduced, he wandered forty-two years in Africa, and arrived, with his family, at the altars of the Philistines, by the Lake of Osiers. Then passing between Rusicada and the hilly country of Syria, they travelled by the river Malva through Mauritania as far as the Pillars of Hercules; and crossing the Tyrrhene Sea, landed in Spain, where they continued many years, having greatly increased and multiplied. Thence, a thousand and two years after the Egyptians were lost in the Red Sea, they passed into Ireland, and the district of Dalrieta.
Here Nennius not also tells us the source of his story, but vouches for their credibility as "the most learned". I don't think we can get much better than that for the time period. Within this account we can see what is still likely to be an embellished story in the connection to Egypt and Moses, but this time we can explain why this might have occurred as part of a journey narrative that happened to include Egypt. (Also the 42 years is too much like Moses 40 years). There is enough detail in this story to suggest it is a pre-Christian origin narrative which has begun to be reformed to fit the Moses story which increasingly becomes the focus of the story in later versions.
Nennius also tells us about the origin of the Picts:-
After an interval of not less than eight hundred years, came the Picts, and occupied the Orkney Islands: whence they laid waste many regions, and seized those on the left hand side of Britain, where they still remain, keeping possession of a third part of Britain to this day.
Note this is very different from the supposed location of the "Picts" which we are usually given which is the North East coast of Scotland** but it fits very well with Bede's statement that St. Ninian went to Whitchurch (SW Scotland) and converted the southern Picts. The discrepancy between Bede's "Picts" and others who attribute the story to "Scots" may be because Bede was using "Picts" not in reference to a specific racial or political group but instead to refer in general to the Scottish elite (who were at that time Picts).
**The location of the Picts is based as far as I can see on the supposed link to place name containing a "pit-" suffix which are common in NE Scotland and their presumed link to symbol stones which also occur in this area. Despite looking I have failed to find any credible link to the Picts. Instead it seems to me the link was probably suggested because "Pit" is close to Peohtas Old English for "Pict". But this link requires the NE to have been Germanic speaking which then means the area was not Gaelic speaking. As far as I can see the idea the NE was Germanic speaking went out of favour, but no one then questioned the supposed link between "Pit" and the Picts. Now many academics will swear blind that these are "Pictish" stones without even realising that there is not one piece of evidence that securely links them to the Picts.
But Nennius appears to have a second source regarding the Scots as he also says:
Long after this, the Scots arrived in Ireland from Spain. The first that came was Partholomus, with a thousand men and women; these increased to four thousand; but a mortality coming suddenly upon them, they all perished in one week. The second was Nimech, the son of...,who, according to report, after having been at sea a year and a half, and having his ships shattered, arrived at a port in Ireland, and continuing there several years, returned at length with his followers to Spain. After these came three sons of a Spanish soldier with thirty ships, each of which contained thirty wives; and having remained there during the space of a year, there appeared to them, in the middle of the sea, a tower of glass, the summit of which seemed covered with men, to whom they often spoke, but received no answer. At length they determined to besiege the tower; and after a year's preparation, advanced towards it, with the whole number of their ships, and all the women, one ship only excepted, which had been wrecked, and in which were thirty men, and as many women; but when all had disembarked on the shore which surrounded the tower, the sea opened and swallowed them up. Ireland, however, was peopled, to the present period, from the family remaining in the vessel which was wrecked. Afterwards, other came from Spain, and possessed themselves of various parts of Britain.
Generally this fits the narrative of an Irish (elite) crossing from Spain, but it contains something interesting when it mentions the separate ships of wives:
After these came three sons of a Spanish soldier with thirty ships, each of which contained thirty wives;
Whilst, Bede's account is generally less credible (when dealing with what was probably seen even then as half fable), it does provide some interesting details:
Now the Picts had no wives, and asked them of the Scots; who would not consent to grant them upon any other terms, than that when any question should arise, they should choose a king from the female royal race rather than from the male: which custom, as is well known, has been observed among the Picts to this day. In process of time, Britain, besides the Britons and the Picts, received a third nation, the Scots, who, migrating from Ireland under their leader, Reuda, either by fair means, or by force of arms, secured to themselves those settlements among the Picts which they still possess. From the name of their commander, they are to this day called Dalreudini; for, in their language, Dal signifies a part.
Clearly the two accounts are different. In Bede the Picts/Scots ask the Scots for wives (and Bede then seems to infer that this led to the descent through the female line of Pictish kings). In Nennius each ship has 30 wives. They appear to be entirely different, but in each origin account the wives are separated out for special mention. This suggests to me that an original story has morphed into two different versions where in each the wives still have a prominent role but only because they were important in some way in the original story.
The fact we have the same basic element, but it has diverged, is I think good evidence that both stories stem from a much older original. Because when stories are made up, they tend to converge toward the familiar. So, they tend to sound more and more like each other because we ignore details we don't understand and embellish with things that are familiar. Therefore, when stories contain details that are not easily understood, it often indicates that these are "fossil" details from a very old form of the story - details which are on the way to extinction because no one understands why they are in the story. And if two different stories derive from one original, we might find that these "fossil details" are kept in the story but are used in different ways.
As such, it is quite possible this story in Nennius in large part derives from an actual story relating the settlement of Ireland or Scotland (but not necessarily of the Scots - as often people "take over" origin stories). It may even be possible to date this from the way it is being embellished by reference to "Moses" by the turn of the 1st Millennium. It is therefore likely to be pre-Christian (< mid 1st Millennium). And more, if it had changed at a similar rate before then, then it is possible to guess its date of origin and I would suggest that at the same rate of change it probably originates at the time of or before the Romans and possibly hundreds (or just possibly thousands) of years before.
But I would not want to leave it there. The Pictish kings may have morphed into the Scots, but they may have been very distinct and separate racial groups (although another suggestion is that the Picts were a political grouping). So, just as the "origin" story of the Jews was included in later versions of the Scottish story, it is quite possible that the story we now have is an amalgam of a "Pictish" origin story and a "Scottish" one.
Indeed, it is not impossible that the reason the Irish stories are so similar to the Scottish one, is that the original story narrating the origin of the Picts (first recorded 297AD) was then narrated to the Irish-Scots who then through cultural links took it back to Ireland from Scotland and then combined with similar Irish stories.
But there are clearly Irish elements, because we learn from Roman writers like Tacitus that the Irish were "like the Spanish". The Roman name for Ireland (Hibernia) was like that of Spain (Iberia). As such it is very likely that there is a Spanish connection as the story suggest. And just to add one last twist - it is also very suspicious that the Picts are first recorded in Britain when there is unrest in the area of Scythia.