[Blas]

The power path to operate the fan should only go THRU the relay not the toggle switch. The toggle switch should ONLY activate the relay. If you have the actual power path for the fan going thru the toggle switch, and then on thru the relay to the fan, it's wired wrong. You say you have the fuse between a power supply and the toggle switch, so you would only be protecting the switch with it, not the fan with it. (if it was wired correctly)
The relays function is to prevent the large power user (the fan) power supply from traveling long distances and the fans large current from flowing thru the little toggle switch. You might also check that fan is turning in the correct direction and not fighting the natural air flow while driving. Hopefully I understand how you have it wired correct? Loose grounds or power can cause this type of overheating problem too. Loose connections = higher resistance = heat.