The extra voltage is dissipated by the regulator as heat, so with 12v input and 5v output and 400mA, you're wasting (12-5) * 0.4 = 2.8w
The heatsink is too small for that much dissipated power.
Here's how to figure out how good of a heatsink you need.
Go in datasheet and look up the thermal data, for example in this datasheet:
http://www.farnell.com/datasheets/1696820.pdf you have it on page 7.
For TO-220 you have:
RthJC Thermal resistance junction-case 5°C/W
RthJA Thermal resistance junction-ambient : 50°C/W
You also have above the maximum operating range (TOP Operating junction temperature range ) which peaks up to 125-150c ... let's go with 125°C.
You have to determine how much can the regulator warm up from the default temperature when it's not working. Normally, you would say the default temperature as 25°C but since your regulator may be in the sun when you parked the motorbike and so on, it's safer to go with 40°C.
So you have now 125°C - 40°C to work with, or about 85°C.
With 12v input and 5v output and 400mA (0.4A), you're going to dissipate (12-5)* 0.4 = 2.8w ...
The regulator has a thermal resistance junction ambient of 50°C / watt meaning without anything connected to the metal back, for every watt of power the regulator will raise by 50°C. In your case, 2.8w will increase the temperature by 2.8 x 50°C which is more than the 85°C margin you have, so it's obvious you need a heatsink.
or in another way.. 85°C / 2.8w = 30.35°C/w .. this is the maximul thermal resistance you have to reach by placing a heatsink on the regulator.
So now the heatsink specs must be : 30.35°C/w - resistance junction-case of 5°C/w - resistance of any thermal paste or silicon pad you put between regulator and heatsink (about 0.5°C/w) - about 0.1°C/w resistance of the thermal paste itself.
Therefore, your heatsink must be rated at 30.35°C/w - 5°C/w - 0.6°C/w = ~ 24.75°C/w
Now that's the maximum value recommended, in practice your heatsink should be bigger... I don't think you want something running 24/7 at 100-110c on your motorbike.
You can go on Digikey or Farnell and sort heatsinks for TO-220 based on this number, 24.75°C/w or smaller.
As a side note: the math above is for heatsinks that are only helped by the air moving around in a case... warm air. If there's a fan blowing over the heatsink, it will work better. Since you mean a motorbike, if you're moving with the motorbike and air blows over the heatsink (you expose the heatsink to air) then heatink will run better. But on the other side, the heatsink may warm up from the bike engine or from sun shining on it all the time (i already counted on this a bit when I said 40c ambient temperature)
The heatsink you have looks like this one, which is rated for 17.4C :
http://www.digikey.com/product-detail/en/581002B02500G/HS387-ND/1216391 Your heatsink is probably at around 20c/w and as you can see, it keeps the regulator working but hot (lower than 125c).
To keep everything happy, you'd probably have to go with a heatsink with 10c/w or less, for example something like this:
http://www.digikey.com/product-detail/en/RA-T2X-51E/RA-T2X-51E-ND/2416489But in your case, it's better to just go with a switching regulator .. get a usb car charger and pop open the case and you have 9-15v+ input, 5v output with much higher efficiency ..
I made a video here about one I bought at sale for about 2$ (or you can make one yourself with the classic mc34063, it's not that hard) :