Imo they should have just clawed 1 or 2 bits out of the ipv4 header for additional routing and called it good enough

This would require new software and new ASICs on all hosts and routers and wouldn't be compatible with the old system. If you're going to cause all those things, might as well add 96 new bits instead of just 2 new bits, so you won't have the same problem again soon.