Ocher stone with coloring scraped out
Mapping involves abstract thinking of course; for example that one thing can represent another. A lot of scientists believe that in order to use things like color symbolism it must be attached to language.
Some recent work by Lawrence Barham of the University of Liverpool has pushed back the date at which humans might have started thinking abstractly to 200,000 years ago, double the previously accepted date. The exciting implication of this work is that perhaps this means language is equally as old.
You sometimes hear it said that mapping as an activity is almost a human universal, and some (eg., Brian Harley) have even said that it predates (written) language. While for many scholars the earliest known map is only 5000 years old (a clay tablet) or perhaps a wall painting from Turkey, this is obviously far short of 200,000 or even 100,000 BCE.
If you include paleolithic art such as the famous Lascaux caves that takes you back to around 15,000 BCE even if this could be considered a "map."
Lascaux cave paintings
Barham's work--if accepted--would force a reinterpretation of the earliest use of symbolic and abstract thought by humans. Perhaps it would also lead to a much older origin of mapping as well?