OP Wrote "have tried new relay, no change, both fans come on before you start up and stay on when you shut the engine down"
So they are still running? Or have you disconnected the battery...
How long do they run after you switch the engine off?
If they start up before you start the engine, I assume they start as soon as the key is turned to Ignition?
What happens if you pull out the low speed fan relay at that stage? Do they stop? If not, then there's a short in the fan to relay wiring. If they d stop, then either that relay is faulty, or its being "told" to supply power to the fans. NCM or wiring.
Have you checked DTC's (Diagnostic Trouble Codes)? I do know uner certain circumstances the fans are switched on as a precaution.