Follow-up are there any records of people's names before written languages? e.g. stories passed down
The subject line is an incredibly broad question. My first reply is that it's like "what is the history of draft animals? what is the history of ships?" in terms of scope.
I have several general books on historical names and naming practices. For example, I like E. G. Withycombe, The Oxford Dictionary of English Christian Names. And may the SOBs at OUP roast for refusing to ever allow it to come back into print and not having an alternative to offer. Sure it's getting a bit old, and I'm told she's generally not reliable in what she wrote about practice outside Britain. But as a long catalog of names with etymologies, histories, and dated verbatim cited spellings (so many historians "normalize" names!), it's great.
"Christian name", in British usage, means what an American would call "first name" and a more precise American (aware of Hungarian and Japanese practice, inter alia) would call "given name" or "personal name".
The third (last, best) edition has an introduction that's xlvii - xii = xxxv pages long. These are the section headings within the introduction:
There's a similar and longer introduction of P. H. Reaney and R. M. Wilson, A Dictionary of English Surnames (again, go for the 3rd ed.). Similarly for Rev. Patrick Woulfe, Sloinnte Gaedheal is Gall: Irish Names and Surnames (a pox on him for using old Irish letter-forms!). And surely others.
So what are you interested in? Given names or surnames (or the fuzzy boundaries between them)? Time period? Language/culture? Location? Any particular aspects?
As for names from before written records: Withycombe ca. p. xv has a page and a bit on Indo-European names. I noted above that I've heard that she was unreliable outside Britain. It looks to me like her reasoning is based on what did make it into written records, and inferences based on known words.
Of the great Indo-European family of languages the general principle was also that of one name for each individual, the majority of names being compounded of two elements chosen from a stock of special name-words. ...
The special name-words of which personal names were composed were originally ordinary significant words, but with the passage of time some of them fell out of use in the spoken language, and others underwent phonetic and semantic changes to which personal names were not always subject. An example of this is the word Os, 'a god', which was often used as an initial element in Old English personal names, but is hardly ever found in independent use, having become obsolete at an earlier date than any written records of the language. (footnote 1: It occurs once, in the plural, in the Charms.)