Origin of the thesis-degree procedure
(note: I have no references for the below, nor am I qualified in the topic)

First of all, the premise of your question isn't quite accurate: certainly in the UK it's very common for undergraduate degrees to have no thesis requirement. But putting that aside:

I think there are parallels with other mediaeval professions, which required proof of skill in order to become a member of a guild (the professional organisation). To be a 'master' of the guild one had to produce a 'masterpiece' (the origin of that word); this has obvious parallels with the idea of a thesis proving that an individual should be admitted to a degree (remember that historically a degree is more like a rank than an award, honour or qualification).

The MA at Oxford and Cambridge is still awarded automatically to those with a BA seven years after the start of the degree, which I believe matches the time someone in a professional guild would take to become a master.

Note also that the modern doctorate is a much more recent invention than the MA.