Are these domain aliases or addon domains?
Been saying it for quite a while (ever since the SSL for everyone craze started), cPanel needs to move away from domain aliases and towards addon domains with shared DocumentRoots.
Domain Aliases (parked domains) just adds the domain to the ServerAlias directive in the web server configuration. If you have 10 domain aliases, then a single VirtualHost in the web server configuration is responsible for 11 domains (the main domain + the 10 domain aliases), so a certificate has to be generated for all 11 domain names. (And regenerated every time one of those domains is added or deleted from the domain alias list)
Addon domains create their own VirtualHost containers. So if you have 10 addon domains, then you have 11 VirtualHost containers - the main domain + the 10 addon domains. Each VirtualHost can have it's own certificate. So you'd actually have 11 certificates generated. When one is deleted... so what? The certificate doesn't get automatically renewed when it's renewal comes up. Want to add an 11th addon domain? Just generate a new certificate for that 11th domain name.
Now... having said all of that... I actually have no idea how cPanel's AutoSSL works in regards to this. I could forsee the issue with domain aliases and certificate (re)generation, so I implemented my own solution. My "AutoSSL" doesn't depend on anything that cPanel does with automatic SSL generation. So I may be speaking out of turn here.
Additionally, I would agree that 3500 domains on a single cPanel account is probably an extreme edge case and doesn't reflect the intent of cPanel. When you get into edge cases like this... you really can't expect the software to work the same as it does for everyone else the uses it within the realm of intention. There's likely always going to extreme cases where a user wants a piece of software do to something it's not specifically designed for, but the issue is that the user is "one" user. The other 99,999 users use the software within the bounds of intention. I would not expect a developer to bend over backwards to appease that one user if there's no justification for the other users.