Many of these will be ground and power, which directly terminate into plane(s) and aren't routed. Things like memory buses are put onto the socket such that they are routable to the memory sockets (the location/orientation of the memory sockets is prescribed by the processor socket!). Other interfaces are arranged to "make sense" as well.
I expect it's pretty much the same problem overall as with the (much smaller) pinouts of SoCs and such.
My guess is that the socket side of this is done during development by AMD and then given to the manufacturers directly so that they don't have to do that part. The only other way I could think of is if the tools have a way to lay out as many of the traces in parallel (i.e. tell it, all of these traces are going to the same place just offset a little) and then do most of that automatically for say the RAM and power. I think most of the length and impedance matching is already automate-able in Altium and other high end software.
Not really, autorouting is generally extremely bad. Especially for applications with such high performance criteria. On the plus side the work only has to be done once since later motherboards are mostly just iterations on a previous design.
The latest high-end PCB tools actually provide useful autorouting features, because they have figured out that if you combine human ability to solve the difficult pattern-recognition and planning problems, you can have a computer solve the details.
Routing 4094 signals sounds daunting, but it is a bit less daunting when you realize that a good fraction of them are power/ground (and route directly to planes), and the rest of them are mostly logically organized into buses/groups that can be routed together.
Yeah, a good portion of those pins will be wired directly to the power regulator components that are next to the socket, and a good chunk more break out neatly into channels for memory and PCI-e.
Seems like it's almost boring these days since everything's encapsulated in a layer of abstraction. A lot of the more complicated wiring is in breaking out PCI-e channels into things like ethernet, audio, and other miscellaneous ports that involve good chunks of analog circuitry.
I expect it's pretty much the same problem overall as with the (much smaller) pinouts of SoCs and such.