Have you actually measured the output of your wallwart with the arduino connected
If that measures OK (<12volts) measure the current being drawn by the arduino.
The heat developed by the regulator is (Vwallwart-5) x Iarduino watts
Anything more than around 0.2 will cause the regulator to get somewhat hot since there is no heatsink fitted
Voltage regulators are specified as being capable of quite high input voltages and high output currents but these only apply if adequate cooling facilities are provided. Without a heat sink you can have reasonable voltage drop but only at very low currents.
If voltages and current are reasonable you could try adding a heatsink to the regulator