Yes, the legends are medieval in form, but words go back. If Lloegr is simply the Welsh word for England, where did that come from?
The concept of names for areas of land is in no way medieval in concept. Even tribes have names for their land - but here we are talking about what was a Roman province, which certainly had its own name and names. Cornwall and Kent were accepted terms within Britain from an early date - as indeed were Mercia, Diera and Bernicia.
Jeanie: thanks, I'm not sure if it helps but it is interesting.
Methinks this thread should be dropped from folklore down to BS, if anyone cares?