No you should not do this. Sometimes it is explicitly allowed on the data sheet (but not that I can see on this data sheet), and when it is, in my experience you never get as much as double the capacity.
Paralleling physically separate relays is worse again because they're not physically moving together- expect welded contacts etc. if you tried that.
If you can split the load (for example, instead of a 40A heater use two 20A heaters) then you can get an equivalent functionality.
You could think about ballasting the loads (wasting power to roughly equalize the currents) and fusing each contact separately, but I don't think that's a good idea at all.
Note that using the relay at the maximum rated current will lead to a pretty short life (only 100,000 operations for a resistive load), which might be only weeks or months if it's switching continuously. At 3HP (motor load), the life is only 1,000 operations, so at once per minute it won't last a single day.
Edit: With the added information that you're using the relay to switch effectively at a relatively low DC voltage and you're mostly concerned about carrying current.. I can't say categorically this is really a horrible idea with a single relay, but I think I'd get on the horn to the manufacturer and see if it's possible to get any buy-in. It comes down to variability in contact resistance vs. the resistance of the connections (plus whatever, hopefully balanced, resistance you add externally). When one of the contacts inevitably fails first, I think I would prefer the relay to not emit excessive amounts of smoke or flames). I think you're okay at 40A (with AgCdO contacts) given the UL508 rating, but beyond that is in question.
If you really need such a high carrying current, the Omron G7Z appears to explicitly allow paralleling the 40A contacts without derating, for 160A total capacity, but perhaps not with the blessing of safety agencies.
That wide range between min and max current is a problem for most relays.
You have a couple of options.
Use a solid state device. MOSFETs are good at low potential and high currents.
Use two different relays: one for the pull-in, the other for holding.
You will have to control both relays individually - the smaller holding relay will pin much faster than the large relay.
Best Answer
Relays aren't perfect switches, and will have a certain contact resistance, which may be several tens of milliohms. In power applications this has to be taken into account. A relay with a contact resistance of 10m\$\Omega\$ carrying 16A will dissipate 2.5W in the contact!
It has been suggested that contacts tend to weld more on opening than on closing. I don't think that's correct. Firstly, in most relays release time is much faster than operate time. Secondly, yes there is often a nasty arc when opening, but that arc is actually a sign that contact anode and cathode are in fact separated, and then they can't weld anymore. That doesn't mean that arcs are harmless. They're a powerful HF transmitter and cause much EMI. And they burn the contact's coating. In AC switching they will extinguish on the zero-crossing, after maximum 1/100 or 1/120 second (doesn't count for very high voltage switching), but in DC this may take longer. That's why DC ratings for a relay will be significantly lower than AC ratings.
So contacts tend to weld upon closing, and you rightly mention that the contact resistance isn't minimum yet during the inrush, so it looks strange that exactly then a higher current is allowed. It's all to do with time. Closing a contact usually takes several ms, but most of that time is used to build the magnetic field in the coil and the travel of the contact's anode also takes some time. The actual time between first contact and final closure is very short. Add to that that the current isn't 80A yet at the first contact; current can't go from 0 to 80A in a nanosecond. So while the current builds up, the resistance decreases. All in a very short time, so that the total dissipated energy in general won't be too high.
For situations where this isn't good enough there are relays with a separate faster tungsten contact to improve closing performance. (In Dutch it's called "voorloopcontact", I don't know the name in English.)
Further reading:
Tyco application note: Relay Contact Life