As mentioned here, the difference between the version of Old English spoken in Northumbria around the year 800 and Old Norse as spoken by the Vikings (basically Old Danish) was much less than the difference between classical Old English and classical Old Norse. So, Northumbrian must have evolved to become similar to Old Danish well before the Viking invasion. This could perhaps be explained if there had been a large migration from Scandinavia to Northumbria, but that doesn't seem to be the case.
It appears that he's saying (starting at about 1:40 in) the "typical standardized form" we are familiar with for Old Norse and Old English are the Old Icelandic sagas (1250AD), and Late West Saxon (1000), which bakes in an extra few hundred years of linguistic drift over 800's northern England.
So the two would have been a bit more mutually intelligible back then than their modern written forms we have access to today, since those modern written forms were created centuries later.
That's the argument, and it certainly makes sense from what I know of linguistics. Language = Dialect + Time. But of course he's got a PhD in it, and certainly doesn't need my endorsement.
As for how they got similar in the first place, well rebalance that equation. Once upon a time they were the same language. Or rather, they didn't exist yet, and there was just a Proto-Germanic Language. Here's a map showing the Germanic tribes that spoke it as they first started moving from Scandanavia down into Europe, broken down by time.
At that point (1AD), these proto-Germanic speakers' common language started to settle into regional dialects (not full blown separate languages yet), as shown in this map.
According to the map the North Germanic dialect became the Proto-Norse language 300 CE. The North Sea Germanic dialect also became its own language, then branched off into 3 dialects, one of which was Old English. Most likely the language spoken by the ancestors of modern English and Frisian was one and the same until these North Sea Germans first came to England to stay, around 500 AD.
What this means is that when the two peoples' came into contact in northern England in 800AD, there was about 500 years of drift between their tongues, plus the further 300 that caused linguists to decide the Norse dialect was now a language. Linguistically, that is a lot of time. The additional delta he's talking about to get to our big written exemplars is a further 400 years, which is also a lot. So he's got a good point there.
Going back to the basic point, were their languages mutually-intelligible? Again, I'm an amateur, but it seems unlikely to me. Heck, I have trouble understanding Jamaicans talking to each other, and that's only about a 300-400 year difference at best. However, when talking to me those same Jamaicans use a more standardized English that I have little trouble with. Perhaps that may be our clue?
I'd say more likely the Norse in particular, being a seafaring people, likely learned to speak the language of their neighbors, and of course the similarity of the languages and the proximity of the peoples' throughout their separate development likely made that task easier1. So if there are tales of them being able to communicate, that's likely why.
1 - On a further listen, this seems the exact point he's making at about 15:22, and his closing at 21:00