Hi.
It is heating up, because you have it backwards. It acts as emitor follower and even worse, the body diode keeps it open the whole time. (just try to draw a line where the current flow. From +12V, to +12V pin on the fan, to pin 3 of the transistor and you get that the diode is in the forward direction to pin 2).
Swap pins 2 and 3, and while keeping the resistor between pin 1 and 3 (you probably don't need the bipolar transistor) make the value lower (I would say even 4k7). When the transistor is switched off, its input capacitance (which is high: 1nF) is discharged through this resistor. From 680k and 1nF you get 680us time constant, which is too high.