I can't think of an easy way to do it. But your technique" could work if you "melt" the cube in layers. A cube of ice wouldn't just "scale" down. Rather, it would melt in layers, from outside in.

Alsmo, if you make a nice "ice" shader it could work...

Please let me know if you find a good way to do it. I would be interested to know.