Stories of giant animals may be younger than 40,000 years if the stories are based on skeletons.
Oral or written tradition is not the only way passing information through generations. A document claimed that aboriginals living close to the Great barrier reef have traditional dances describing the birth of the local barrier reef. The traditional dances tell the story how humans needed to retreat from the coast as water was rising. The document told that happened around 10,000 years ago, if I remember right.
True or not, it is likely that stories about crucial events may be told thousands of years, especially if the society gives the task to a valued group of individuals, such as religious leaders. Younger persons in training may need to recite and learn the stories from word to word before they gain a valued position. If the training is less intensive, parts of the stories may change while the core of the story is preserved.