Each time you attack, as long as you actually hit you are doing damage and so it will eventually die if you just followed it around.
However, there's a few other things you can try - sometimes the Nymph might attack a floating eye and be frozen, allowing you to attack it freely.
If you have a pet, and they attack first, this can sometimes allow you to do enough damage before they then manage to freeze you too.
Wands with projectile attacks allow you to attack from a distance, meaning it can't freeze you, or you could polymorph/teleport the nymph away too.
If you're carrying a mirror (?) then the nymph will always take this first and depending how quickly you unfreeze then you maybe able to kill it immediately after it takes this.
Also you could go extreme and just genocide all the nymphs, tho I believe they do drop some useful items.
The most obvious tip tho, is to not drink from fountains, until you're ready to take on everything that can spawn from them...