Taking a look at the diagram, it's a little blurry when I zoom in, but the relay connector has:
Two green wires 12v+ from the fan fuse
A blue/red power to the fan
And purple/blue power from the ECU.
Colors look like BL/R and P/BL, I might be off because of the blurry zoom. Either way, it seems you should be looking for the 12v signal from the ECU.
If it's powering the p/bl wire, then it is purposely running the fun. That's no bueno. Keep looking for wiring issues, double check your new sensor, or replace the ECU.
But if you don't have voltage there. Then the relay is misbehaving and sending 12v out the bl/r wire to the fan anyway and needs to be replaced.
I hope I'm helping.