Hot water heater
The phrase is definitely grammatically correct (it has no objective construction or structural issues). Whether it's appropriate usage or not is a different a question.
I can think of two ways to parse the phrase:
Hot [water heater]: a water heater that is hot.
You know, because... it gets quite hot... as it heats the water.
[Hot water] heater: a water heater which further heats water that is already hot.
If you live in a desert, this might somewhat apply.1 I do not know if there are special appliances for heating water that's already hot.
Short, nice answer
The phrasing is, indeed, somewhat redundant, unless there is a very special case that holds. A heater of object X does conventionally make object X hotter.
 Getting water when in a desert is a separate problem.