Should I upgrade my CPU Cooler's fan?

Solution
You can upgrade your CPU cooler's performance if you like.
I take that your CPU cooler did came with 4 wire clips to mount the fan, so you can upgrade your CPU cooler from push configuration to the push-pull configuration.

If so, you can buy 2x Noctua NF-F12 fans,
specs: http://noctua.at/en/products/fan/nf-f12-pwm
pcpp: http://pcpartpicker.com/product/b2vRsY/noctua-case-fan-nff12pwm

If you don't like the looks of Noctua fans and want to have more eyecandy by the LEDs with better performance, then go for Corsair ML120 fans,
specs: http://www.corsair.com/en/cooling/ml-series-fans?fansize=120mm%20x%2025mm|
pcpp: http://pcpartpicker.com/products/compare/LkJkcf,wPFXsY,MpBrxr,GXkwrH/

In my Skylake build (full specs in my sig), i replaced...
You can upgrade your CPU cooler's performance if you like.
I take that your CPU cooler did came with 4 wire clips to mount the fan, so you can upgrade your CPU cooler from push configuration to the push-pull configuration.

If so, you can buy 2x Noctua NF-F12 fans,
specs: http://noctua.at/en/products/fan/nf-f12-pwm
pcpp: http://pcpartpicker.com/product/b2vRsY/noctua-case-fan-nff12pwm

If you don't like the looks of Noctua fans and want to have more eyecandy by the LEDs with better performance, then go for Corsair ML120 fans,
specs: http://www.corsair.com/en/cooling/ml-series-fans?fansize=120mm%20x%2025mm|
pcpp: http://pcpartpicker.com/products/compare/LkJkcf,wPFXsY,MpBrxr,GXkwrH/

In my Skylake build (full specs in my sig), i replaced my CPU cooler (Arctic Freezer i32) fluid dynamic bearing fans with Corsair ML120 Pro red LED magnetic levitation bearing fans to match the black & red theme of my build while gaining better CPU cooling performance.
Here are also few pics of my setup: http://www.tomshardware.co.uk/forum/id-3272328/show-newest-system-upgrade-components.html#19158458
 
Solution

There is no cooling performance gain over air coolers if you go with AIO water cooler. Only benefit of the AIO water cooler is that there is no RAM clearance issues with AIO water coolers. Air coolers benefits include: lower purchase price, lower noise and less maintenance.
 
Just got the ML fan installed and ran a quick test comparing both the stock fan and ML fan using 10 minutes of Prime95. The results are pretty disappointing. My stable overclock runs at 1.344v max.

Stock fan full load:
Core 0=81C
Core 1=85C
Core 2=78C
Core 3=85C

Corsair ML fan full load:
Core 0=80C
Core 1=85C
Core 2=76C
Core 3=84C

No real difference at all. I will say that by the sound of the Corsair ML fan at MAX RPM, I thought it should have cooled my entire house down. It is LOUD! Like hoover vacuum cleaner loud. I was shocked after reading the reviews, I expected this fan to be at least as quiet as my stock fan, not 10 times louder. Of course this is at full load, it is whisper quiet at idle. Not all is lost however. I have a fan that doesn't have the static pressure to overcome my cases filter, this fan will take it's place. Expensive replacement though. Oh well, live and learn.

 
I take that you run your tests with 1 fan on heatsink (probably in push configuration), right? If so, try running your Prime95 again with 2 fans on heatsink, in push-pull configuration.
Do note that my initial suggestion was about push-pull configuration and not just about single fan replacement.
 
I did try a push pull as well and it made no difference in temperature. Makes me wonder if my cooler is not attached properly. I am going to reapply thermal compound as soon as it comes in the mail.
 

I see, thanks for the answer!