I really wish that you would define what you mean by "mythology" and "recorded". The word "mythology" is one that has several competing definitions, and it's not a word that is used frequently by academics. It would have really been nice if you had explained what definition you meant. Similarly, by "recorded" do you mean written down, or can paintings/art count? Not explaining these things makes it hard for me (and others) to give a good answer.
If by recorded you mean written down, and if by "mythology" you mean sacred narrative, then one of these two texts would probably fit the bill:
The "Instructions of Suruppak" and the Kesh temple hymn still represent unique cases, but there is no reason to assume that archaic fragments of other Sumerian compositions known from the Old Babylonian period will not one day be found.
(Source)
You might also consider Paleolithic Cave Art, although there is considerable debate as to the function of the art (to put it another way, we don't know if the art was religious or decorative or etc. etc.). That might effect whether you would consider the art "mythology". We also don't know whether the art is the recording of a story, which might also effect whether you would consider it "mythology"/sacred narrative.
UPDATE: in the question text mythology was defined as a "system of beliefs." That's not a definition of mythology that I've seen anybody use (again, if you would like to read accepted definitions of mythology you should take a look at my blog post on the subject); a better word for "system of beliefs" would be "religion. So I'm going to assume that this question asks "what is the oldest recorded religion?"
There is considerable debate over whether Paleolithic Cave Art is religious in nature. But assuming it is religious, then it would quality as the oldest "recorded" evidence of religion.