If the following seems too long, you can directly jump at the end for the conclusion ins the TL;DR section.
I'm not an historian and (almost) everything I tell below comes from internet research. More precisely, the whole stuff I tell below finds its source in various articles by the assyriologist Jens Høyrup.
The king and the chess board in Indian and Islamic tradition
This legend is very common and universal, I remember my father telling me this story in Paris the 1980's. Less anecdotally, Stith Thompson gives a place to this motif in his folktales-motif index (Z21.1).
Georges Ifrah tells a variant of it in his Universal history of numbers [3,4], where the king's accountant does not manage to compute the doubling because he uses an abacus, which makes these big numbers impractical. The wise man was then the the only one able to count how many grains of wheat were needed, because he used the 10 digits of what we now call the Hindu-Arabic numeral system. Chess and Hindu-Arabic numerals where both find their origins in India in the middle-ages, and both followed the same Persian route towards the Islamic empire, there association in this mathematically themed legend might point to the origin of this 64 doubling problem.
According to , the last chapter Abu'l-Hasan al-Uqlidisi book on arithmetic with Hindu numeral is On Doubling One, Sixty-Four times. This book was probably written in 952. Apparently, Al-Khwārizmī, who died a century earlier, wrote a (lost ?) treaties on the question. Jens Høyrup states in  that
[this] tale is found in various Islamic writers from the 9th century onwards;
he mentions a text by al Ya'qubi, [2, note 30].
This text should be older than Firdowsi's text mentioned in astabada's answer. Given the association of the number 64 and the chessboard, older versions of this legend might be found in Indian texts between the 6th and the 9th century.
However, as seen below, this story has much older roots.
A variant of an older mathematical folktale: the 30 doubling problem
Something I find interesting, is that popular these doubling problems/riddles/tales appear only in two forms: either one doubles 64 times, or one doubles 30 times. This observation has already be made by al-Uqlidsi in 952:
This is a question many people ask. Some ask about doubling one 30 times, and others ask about doubling it 64 times.
This implies that all these tales are somehow related, and that cannot be interpreted as independent discovery of the exponential progression! Furthermore, the variant with 64 doubling only appears quite late, at a time were the chessboard (and hindu-arabic numerals) existed. Furthermore, the "obvious" relation between 30 and the length of a month seems to only appear lately, so it is probably not the source of the number 30.
And actually, the 30 doubling problems, with other recreational mathematical problems are spread over a vast area, from western Europe to China and [1,2] following  attributes it to:
the community of traders and merchants interacting along the Silk Road, the combined caravan and sea route reaching from China to Cadiz.
(I have no access to ref  which is long book in German, but I'd like to!)
The narration around these 30 doubling problems is often different than the chessboard tale, except maybe for the earliest. I'll give here some examples in reverse chronological order.
21st century CE: Today's version, still alive!
If you search for "double a penny", you'll find that the modern avatars of the old "community of trader" still propagate the same story. The narrative round these two examples correspond exactly with the proposed context in Høyrup's paper!
8th century: Carolingian Europe's king's problem
The 13th problem Carolingian recreational mathematics treaty Propositiones ad Acuendos Juvenes (en: Problems to Sharpen the Young), maybe due to Alcuin, has a very different tale to this 30 doubling problem :
The Latin version, from Vikifons (i.e. latin wikisource).
XIII. PROPOSITIO DE REGE.
Quidam rex iussit famulo suo colligere de XXX uillis exercitum, eo modo, ut ex unaquaque uilla tot homines sumeret, quotquot illuc adduxisset. Ipse tamen ad uillam primam solus uenit; ad secundam cum altero; iam ad tertiam tres uenerunt. Dicat, qui potest, quot homines fuissent collecti de XXX uillis.
In prima igitur mansione duo fuerunt; in secunda IIII, in tertia VIII, in quarta XVI, in quinta XXXII, in sexta LXIIII, in septima CXXVIII, in octaua CCLVI, in nona DXII, in decima ¬I XXIIII, in undecima ¬I¬I XLVIII, in duodecima ¬I¬I¬I¬I XCVI, in quarta decima ¬X¬V¬I CCCLXXXIIII. In quinta decima ¬X¬X¬X¬I¬I DCCLXVIII, etc.
Its English translation, by J. J. O'Connor and E. F. Robertson, at the MacTutor history of mathematics archive is:
13. Puzzle of the king's army.
A king ordered his servant to collect an army from 30 villages as follows: He should bring back from each successive village as many men as he had taken there. The servant went to the first village alone; he went with one other man to the second village; he went with three other men to the third village. How many men were collected from the 30 villages.
(I don't reproduce their modern solution.)
1st century (CE or BCE): a Ptolemaic papyrus in Egypt
In  Jöran Friberg (de.wiki,publications) mentions the Ptolemaic papyrus
P. IFAO 88 transcribed here. This manuscript simply corresponds to the calculations (with a mistake !) of 30 doubling of 5 (ε) copper drachma (either a monetary unit (like the modern penny above) or a weight unit.)
Jöran Friberg speculates The presence of this text in Egypt might be connected with with the medieval chess legend, since the Egyptian game of Senet has 30 squares. However, it is only a speculation, and as much as I would like to read about an Egyptian legend involving a Pharaoh, the inventor of the game of Senet, and single grain of wheat doubled at each square, I'm not ready bet a few grains of wheat for the finding of such a papyrus !
As noticed by Jöran Friberg, this text is also parallel to a much older texts, where the smallest weight unit is called a barley-corn (see below).
18th century BCE: an Old Babylonian cuneiform tablet from Mari
The oldest written source of the 30 doubling problem is the cuneiform tablet M 08613, from the first half of the 18th century BCE (according to the middle chronology). This tablet is heavily discussed in [1,2,6].
As the Ptolemaic papyrus, this tablet only contains the computation of 30 successive doubling of a small weight unit (~0.05 g). However, this time, the unit is litterally called a "barley-corn". The text starts this way (translation from [here]((http://www.cdli.ucla.edu/P390441)
A barley-corn: to a single barley-corn I increased,
2 barley-corns in the 1st day;
4 barley-corns in the 2nd day;
8 barley-corns in the 3rd day;
and so on (including the unit changes and various problems and errors linked to Mari's specific centesimal/sexagesimal number system). It ends at the reverse of the tablet with
1 ‘thousand’ 3 ‘hundred’ 48 talents 30 minas 16 1/6 shekels 2 barley-corns in the 29th day;
2 ‘thousand’ 7 ‘hundred’ 37 talents 1/2 mina 2 1/3 shekels 4 barley-corns in the 30th day.
If I understand correctly the comments ‘thousand’ should in fact be read as sexagesimal 600, and ‘hundred’ as sexagesimal 60. Any way, the final weight corresponds to slightly less than 50 tons. It is likely that this computation was linked with a narrative, but the fable has not be found (yet).
Høyrup explains that the position of Mari, as well as the originality in style of this tablet (it's not a standard scribe exercise) makes the connection with a merchant's tradition likely.
TL;DR: The answer to your question
To make long story short. Your questions were:
What are the origins of the fable? More specifically, and since chances are the fable was passed down through oral tradition, what are the earliest recorded instances of it?
My (or in fact Høyrup's and Friberg's) answer is:
- The origin of the fable can be traced back to the 18th century BCE in Mesopotamia.
- Computations related to the fable are recorded in the cuneiform tablet M 08613 which is the earliest instance of it.
- This tale was transmitted, along with other mathematical riddles along the silk road on a wide area, ranging from western Europe to China. It was probably transmitted by merchants, and various modern versions are still alive on the internet.
- Jens Høyrup, Sub-Scientific Mathematics. Observations on a Pre-Modern Phenomenon. History of Science 28 (1990), 63–86. It can be found at page 394 of this big pdf file.
- The Formation of «Islamic Mathematics». Sources and Conditions. Science in Context 1 (1987), 281–329. pdf
- George Ifrah, Universal History of Numbers: From Prehistory to the Invention of the Computer. Translated by David Bellos, E.F. Harding, Sophie Wood and Ian Monk. Harville Press, London, 1998 (ISBN 978-1860463242).
- George Ifrah, Histoire universelle des chiffres, 2nd edition. (Seghers, puis Bouquins, Robert Laffont, 1994)
- Tropfke, J./Vogel, Kurt, et al, 1980. Geschichte der Elementarmathematik. 4. Auflage. Band 1: Arithmetik und Algebra. Vollständig neu bearbeitet von Kurt Vogel, Karin Reich, Helmuth Gericke. Berlin & New York: W. de Gruyter.
- Jöran Friberg (2005) Unexpected Links between Egyptian and Babylonian Mathematics, World Scientific, Singapore (Reviewed by José Barrios Garcia, Metascience (2007) 16:295-298) isbn:981-256-328-8, Chapter 1: Two Curious Mathematical Cuneiform Texts from Old Babylonian Mari (830 KB)