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.