Stepper Motor works at 5v, driver explodes at 12v?
While bipolar stepper motors require a quad half bridge driver, your unipolar motor has center tapped coils that can be driven by a simple transistor array such as the uln2803.



simulate this circuit &ndash; Schematic created using CircuitLab
Freewheeling diodes are required to prevent the inductive kickback caused by the coils when the transistors switch off from destroying the transistors, but the transitor array you selected already has integrated freewheeling diodes. Judging from the pictures you posted, the COM pin is connected to the supply voltage: the diodes are properly connected.
Looking at the datasheet, the individual transistors can only sink an absolute maximum of 500 mA each, and the entire chip can sink a total current of only 2.5 A. Placing two transistors in parallel (as you have done) doubles the maximum current in theory, but with bipolar transistors this is not always the case in practise. The transistor that heats up more will have a lower forward voltage and thus tends to gobble up an even greater portion of the total current causing it to heat up even more in a feedback loop.
This is not the case with the ULN2803, however. The transistors share the same die and are actually designed to be paralleled, obviating the problem:

The problem
It appears that the collector current is too high at 12V. Currently the only thing limiting the  collector current is the winding resistance, and the same resistance at 12 V will pass 2.4 times the current it passed at 5 V. You have three options for correcting this:

Use a bipolar stepper with more turns of finer wire

Add two current limiting resistors. A resistor should be connected between each center tap and the supply voltage, and should have a value that when combined with the winding resistance limits the current trough each transistor to (preferably much) less than 1A. The COM pin should still be connected to the supply voltage.

Pulse-width modulate the coils. By lowering the duty cycle, you can lower the effective motor voltage. This has the advantage of higher efficiency and that you can increase the motor voltage when the motor speed increases, countering the back-EMF generated by the spinning rotor and better maintaining torque at speed. The disadvantages are that switching losses will be generated even when the motor is at rest, the constant pulsing will generate coil whine and the code will necessarily be more complex.