What can happen to a relay at temperature outside of its spec?
I wonder what else can happen to a relay when it is used at a higher
  and lower temperature than specified?


The first thing that it will do is cease operating in a manner consistent with the datasheet. This means that the component is no longer guaranteed proper functionality. Many manufacturers also test components to the operating temperatures listed in the datasheet, and if you run it outside of that temperature, the results will be unpredictable.

Many epoxies and plastics start to degrade and deform at ~120C, the lose their properties. The metals will probably be fine.

For a relay, there is also additional power dissipated in the coil, which raises the temperature beyond the ambient (environmental) temperature, so I would imagine that most relays are also have a de-rated operating temperature, from the storage temperature for this reason. 

If the design is tolerant for failure (meaning you don't mind failure and replacing the parts), then run it outside of the operating temperature range. If you need reliability, then don't.