The nut in the back of the fan clutch that screws onto the water pump is left-handed thread.
You need to make or buy a tool to hold the pulley still while you loosen it.
I bought a strap of steel from the hardware store, about an inch and a half wide and 1/8" thick and two feet long. I used the new water pump to get the distance between the bolts, and drilled two holes in the strap just big enough so the holes would fit over the 10mm bolt heads in the pulley. Then I ground a half-moon shaped notch in the side of the strap between the holes so it would fit around the pulley shaft.
With my home-made tool fitted over the 10mm bolt heads to hold the pulley from turning, I used a thin-jawed crescent wrench to loosen the big left-handed nut.
The water pump presses in to a hole and is sealed with an O-ring. It is pretty tough to break loose after 14 years, but once it starts to move you can pull it out.
While you are there, replace the thermostat and housing. Don't try to re-use the old plastic thermostat housing because it will have shrunk and warped and if you re-use it, it will leak. I use aluminum replacement housings because they are actually cheaper than plastic and they seem to work fine.
Use BMW coolant. Do not, under any circumstances, use organic acid coolant (aka Dexcool). BMW coolant is cheaper on line than from the local dealer, but it is a little late to think about that.