S8050 BJT is rated for 700 mA but gets extremely hot when powering a 12 volt 700 mA PC fan
From your description it sounds like you're doing "high-side switching", like this:







simulate this circuit &ndash; Schematic created using CircuitLab

THIS IS NOT WHAT YOU WANT!
Because, as you've discovered "the fan doesn't spin very fast", this configuration will never deliver the full 12V to your fan.
It doesn't matter if the Arduino is there or if you're just pulling that pin manually up to 5V.
In this configuration your fan will never get more than about 4.3V (5V - 0.7V Vbe), with the remaining 7.7V dropped across your transistor (just causing it to heat up - as you've also discovered).
The voltage at your NPN transistor's emitter can never get higher than the voltage you put on its base (minus the typical 0.7Vbe).

Rearranging your circuit to do "low-side switching" instead will improve things dramatically:  







simulate this circuit

In this configuration with the emitter tied to ground, applying 5V to the base resistor (not directly to the base) causes the transistor to switch on 'hard', pulling its collector down to about 1V, which means that your fan now gets 11V - much better than before.

While this is a significant improvement, its still a bit less than ideal.
The low-ish current gain (probably around 40) means that your poor Arduino will have to source around 15-20mA to drive the transistor (and you would need to reduce the value of the resistor to 220R or less).  

Replacing your S8050 NPN BJT with a small N-Channel logic-level MOSFET (also in the low-side configuration) should give an even further improvement.
You can do away with the resistor and connect the N-FET's gate directly to your Arduino while not worrying about the Arduino having to source any current, because the N-FET doesn't really require any. *simplification
IF you choose the right N-FET you'll also get closer to delivering the full 12V from your supply yo your fan.