What fan really pulls that much? If it's 2 fans, use 1 relay for each. The problem you're running into is that standard size relay terminals aren't really up to the task, nor are the contacts you find in a standard auto electrical center. It's very important to use good crimps (or solder), or the heat can melt the plastic base of the relay and it will fail. You can push the current by using non-standard terminals, but instead ones with a bunch of contact points. This may not be available in a pre-made relay socket. And of course, you have to use heavy wire. The copper pulls heat out of the contact.
40A is a standard rating for automotive relays. You just have to step up to the larger contacts. You could use a contactor/solenoid type to upgrade to ring terminals, but they are inefficient and noisy and you have to choose a continuous duty type.
Any interest in solid state?