In this paper in Nature, the authors argue that all human beings share the same set of common ancestors as recently as three thousand years ago, and that all Europeans likely share the same set of ancestors from only 1500 years ago. So in other words, if a European from the year 500 AD has any surviving descendants today, then it is highly likely that all Europeans alive today are among his descendants. This is based on a statistical model of interbreeding and average time between generations and so forth, and not based on tracing actual lineages back 1500 years.

Charlemagne lived about 1200 years ago, but he had 20 children, so I do not think Fry's claim is at all far-fetched.

An explanation of the findings by the authors for popular audiences is here.

I was just watching a performance Stephen Fry gave in Sydney, Australia in 2010, in which he told the crowd that if they had English or Scottish blood, they were related to Henry IV (the English one, not the French one). He supported the comment simply by saying, "you have two parents, four grandparents..." and iterated the math to 512, 1024, 2048, 4096, etc.

I'm not sure if the QI claim was in the same context, but he may be basing it solely on the math, as he did in Sydney.