Population recovery time after a fantasy nuclear winter

Question

One of the major events of my setting is an all-out war between two factions of gods (and their human subjects) using basically the magical equivalent of nukes and nuclear technology. The world was bombed to hell and back, firestorms broke out, and everything was plunged into a magical nuclear/impact winter. Humanity was reduced down to only ~10000 people, and all but a handful of the gods are dead, but they're determined to start over. How long would it take for this many people to recover to a healthy population (1-6 million people)? Could they recover at all?

For all intents and purposes, this event is treated the same as a hypothetical nuclear winter, just with "magic" instead of "radiation": it's a bit flashier and weirder than radiation, but with a similar half-life and degree of danger. The world has one continent the size of Africa with varying climates and is flat, Discworld-style, meaning no global jet streams/water currents (just circulating air cells). The remaining humans are not scattered, but in tribes and villages able to reach one another. The gods are physical entities and can help humans and teach them survival skills, but they aren't strong enough to deus ex machina the world back to the way it used to be. They have to work at fixing it, and it could take decades to centuries.

Edit: Fertility rate is around 4.5, and child mortality is around 35%. Healing magic exists but it's difficult to learn, so most people don't know it; each settlement would likely have one healer. The gods are trying to care for humanity, but mostly in the form of "show them how to start society again and then work on maintaining a stable world, checking in on the humans every now and again". Furthermore, they're neither omniscient not omnipotent. The pre-apocalypse world had advanced magical technology available to a privileged few, which included flying constructs, prosthetics and robots. The post-apocalypse world is scavenging what remains of it, but remains at a pre-industrial technology level.

Answer 1

36,000 Years

Given your numbers

Fertility rate is around 4.5, and child mortality is around 35%

A mortality adjusted fertility rate is 2.925, i.e 2.925 children on average are born to each mother that live to grow to adult age (4.5 * 0.65). Now given an average lifespan of a mother of say 65 years (realistic in a pre-technology environment) thats 0.045 surviving children per mother per year. We'll say that around a third of the population are eligible to have children (adult women that are pre-menopause) so we'll divide that number by 3 to reach 0.015 surviving children per person per year. Notably, the IRL current world population growth rate hovers between 2% and 1% per year, or 0.02 and 0.01, which means we must be close to right with our maths

Putting that into a compounding calculation shows that after 36,000 years a starting population of 10,000 people grows to 2,213,167. Of course this assumes that the starting population is evenly distributed by age and several other things like the fertility rate doesnt change over time.

That's a really big amount of time! if child mortality were only 10% (maybe magic and gods helping with sickness) we end up with 2,173,356 after 26,000 years instead. I confess, I'm not a population scientist or historian so there's probably some factors I missed out, but it seemed like a fun math problem to try.