What is the criteria of choosing a given pin pattern in ICs?
It's a complex topic that only the manufacturer can fully answer. There's lots of decisions when it comes to pin bonding, but in short, it's about EMC, internal supplies and internal clocks. The sensitive pins are those for supply, ground, oscillator/PLL and ADC. The GPIO pins around probably the least sensitive ones, so where they end up is the less important.
If you look at the S12Z part, you can see that they have clearly tried to separate analog and digital parts, with ADC and analog comparators to the bottom left, and digital buses SPI/CAN etc to the right. Analog supply at the bottom, oscillator to the left etc etc.
If you dig up the 80 and 112 pin versions of the S12 you'll see how more pins of the same kind expand next to each other. These are typically designed with the 112 pin version in mind and the smaller ones get pins stripped off in order to cram everything down to 48 pins, making the 48 pin version less intuitive than the 112 pin one.
There are many reasons for a particular pin layout.
Historic
Often manufacturers follow precedents set out by earlier parts, particularly when they have to interface to them. The classic example is the layout of address pins in various memories, which tend to be influenced by early single chip CPUs like the 6502, Z80 and 8080.
In your example the part is matching the layout of older parts such as the ATmega8, so that it can be a direct or very close drop-in replacement.
Internal layout
The internal design of the IC may dictate the pinout to some degree. An example would be where the chip has analogue functions, which need to be kept relatively separate from the noisier digital parts of a microcontroller. It is also beneficial to keep the bond wires, the wires that connect the chip's die to each pin, as short as possible to improve signal integrity.
Peripheral mapping
In your example of an ATmega part, most of the pins have peripheral functions. Atmel has a "house style" where, for example, SPI pins are usually on the same port pin numbers and in the same order.
This is not only familiar to designers, but it helps port code between models with minimal modification.
In earlier, simpler days the pinout was dictated by what the silicon layout designer could achieve, the external pin order following closely to the bond pads on the silicon die. For example, in early TTL logic an attempt was made to always have ground on pin 7 and 5V on pin 14 of a 14 pin package, however on the more complex devices this was not achievable at the time. For instance, the 7493 counter had 5V on pin 5 and ground on pin 10.
I have been involved in the design of thick film hybrids, and therefore have seen many logic gates, op-amps, multiplexers, ADCs and DACs etc, in bare silicon, and seen how you can't have bond wires crossing. The modern logic gates are very tiny, not like the old TTL. You can't re-order the pins, but you can rotate the chip into your preferred orientation, which helps a lot.
In the analogue world, most dual or quad op-amps were given a symmetrical layout, like the LM124, but a few were not. But the die layout is critical, and performance gains came from avoiding thermal gradients across the input transistors to minimise offset voltage. Usually a quad of transistors were used, diagonally opposite devices in parallel making the differential pair, but detail like that would not show in the external pinout. However, the position of the output stage, that can dissipate significant heat, will influence the pinout.
The LM124 of about 1974 was a mediocre device (still has some uses), and the need to replace it in high performance designs ensured that almost all high performance quad op-amps follow the same pinout. And so it is with other packages, single and dual, with the exception that the 747 (dual 741) was not replicated, and duals went to an 8 pin package.
Although modern integrated circuits are generally much more complex, faster and lower power CMOS equivalents of most 73 series logic devices are still made. The same pinout is retained, after 50 years, for compatibility reasons, even though the devices are available in much smaller SMD packages.
8 bit memory devices came along when silicon layout techniques had improved, and followed a scheme with the address bits and data bus arranged in order around the device to facilitate laying out the bus on the pcb, with ground and 5V on the corner pins, as usual. The package grew from 24 to 28 and then 32 pins as the memory capacity increased, the original pins being kept in the same physical places with respect to the ground pin, so the added address lines ended up in strange places, and not in a nice sequence. Fortunately ROM/EPROM/FLASH retained the same pins for the main functions, and RAM kept to the same convention as far as possible, so it was fairly easy to change the relative amounts of ROM and RAM in a system, and the bus was consistent between all the memory devices.
Early microprocessors were in some cases arranged to make the bus physically reasonably compatible with the memory devices, but others were notoriously difficult for the layout engineer. Some companies seemed to be more capable than others, but layouts were still being done by hand at that time.
When the time came to mix analogue and digital stuff on one chip, starting with ADCs and DACs, noise was all-important and the pinout reflects that. Only one standard developed for parallel input CMOS DACs of variable resolution, the package getting longer as the number of bits increased. Fortunately most such devices use a serial digital interface nowadays.
Analogue switches again tended to be symmetrical with 4 in a package, one at each set of 3 pins at the end of a row, with the power and grounds in the middle, driven by noise considerations.
By the time the first microcontrollers with analogue circuitry onboard appeared, it is likely that everyone was using CAD for chip design, and with the need to avoid crosstalk between complex digital stuff and analogue the entire layout of the chip had to be carefully considered, and the external pin layout went back to what was possible internally, much as it began. The difference is that now, there is a fair amount of freedom to lay out the digital I/O ports sensibly, with an 8 bit port usually in correct numeric sequence, keeping the analogue stuff well away (ground pin(s) are also very important) so the external layout may end up looking a bit messy. This is not helped by the tendency of some chip designers to try to follow the pinout of some unrelated ancient device like the Intel 8051. But for good analogue performance you don't use the internal facilities in your microcontroller anyway.
When it comes to smart power drivers, class D audio amplifiers and similar, an entire new set of criteria come into play, and the general principle of keeping analogue and digital as far apart as possible still applies, but with the need to avoid thermal gradients in sensitive areas such as the input end of op-amps. So if you see a weird pinout, the manufacturer has designed it that way for a good reason. It is no longer because they were struggling to lay the chip out manually.
The advent of BGA packaging has basically ruined any attempt at rational pin layout. It does give you the opportunity for proper supply distribution and decoupling, as there are multiple ground and supply balls, but you are going to be using some good CAD software and a PCB with many layers to get the I/O where you want it. But at least you don't tend to use parallel data busses in most modern equipment, unless external memory is required.
In summary, the apparently irrational pinouts were, were not, and again are, due to what could be physically designed into the silicon given the design methodology and manufacturing processes of the day, but some of them are solely due to the need to be standard, i.e. copy someone else.
It was also so with valves (tubes) but the complexity level was of course much less.