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.
