One important point that you might not be considering is the heat of vaporization.
You may be aware that while it normally takes 4.18 J (1 calorie) of heat to raise 1 gram of water 1 °C, it takes around 2250 J of heat to raise 1 g of water from liquid at 99.5 °C to gas at 100.5 °C, due to the energy needed to go from a liquid to a gas. - What you may not know is that the enthalpy of vaporization isn't limited to vaporization at the boiling point. Any conversion of water to water vapor requires heat of vaporization, though exactly how much is temperature dependant.
So when water evaporates, it cools things much more than one might expect from the "average" energy (or even statistically above average energy) a water molecule may have in the liquid state - several hundred times more. All this is driven by the entropic benefits of having water molecules in the gaseous state rather than the liquid state.
Wind makes the process more efficient because it removes the water-vapor laden air, unbalancing the equilibrium of the process in favor of further evaporation. More water makes it more efficient (to a point), because there's more water to evaporate and the rate of evaporation increases, increasing the removal of heat.
This is not just a physiological perception effect - one can actually measure the temperature drop when water evaporates. Evaporative coolers make use of this effect, and traditional wet-bulb hygrometers (psychrometers) use exactly this effect to measure the humidity -- in some cases you can get a temperature differential of 20 °C or more between a dry bulb thermometer and a wet bulb thermometer.
There is a small perceptual effect in that the evaporative cooling is happening on your skin, where a large number of temperature receptors are located. Therefore, your skin (and temperature receptors) feel a cooling effect even if your core temperature doesn't change detectably. Local cooling produces a larger temperature change than might be expected if you calculated for a whole-body heat change.