Caveat: My experience is with a 1988 560SL.

By all means do what Doc said. If no fix, before throwing expensive parts at it, check operation of the engine temperature sensor that inputs to the computer. That sensor is a simple screw-in replacement and costs in the neighborhood of $45 to $60. Available here on FASTLANE from Phil.