Frankly I'm AMAZED you made it to 9k leases with dnsmasq. Not only from a performance standpoint but the overall logging, lack of instrumentation, limits in configuration, etc. As you say (from reviewing the source) it's really not intended for anything other than small home/SMB networks, memory and CPU constrained devices, etc. It's perfect for that and it's my go-to in those scenarios. A 10k host network is a completely different animal and from the down-votes my comment received it doesn't seem like many here on HN have been in scenarios like these either.
Your comment about the logging is spot on as well. I think dnsmasq and I think "small flash device where the logs will never get stored anywhere and no one can or will view them anyway". As you can probably tell I've had issues getting meaningful logging and debug out of dnsmasq as well...
I don't envy your situation in the slightest!
Note to mods - I'm not complaining about downvotes. I'm using the downvotes as a sign there's little understanding on HN of network ops at scale. People may love dnsmasq on a home router (I do) but plenty of network admins like OP and I have watched it fall over in other scenarios.