You say "when a solid(ice) melts into water(liquid), the temperature would increase" you are mixing up cause and effect. The ice melts BECAUSE the temp increases....it is not the ice melting that causes the temp to increase.
When water freezes this is an exothermic process- heat is released as weak intermolecular forces between water molecules are formed. A fridge freezer has to work hard to remove this heat generated- feel down the back of a freezer..it is quite warm...black pipes are radiating away the energy taken from the inside of the freezer.
Likewise when water evaporates, it is endothermic (intermolecular forces broken between water molecules) - evaporating causes cooling-e.g. sweating cools you down by causing evaporation from your skin.
It is a bit counterintuitive.