Normal and magic damage essentially do the same thing: they lower the enemy's HP. The difference is that normal damage is augmented by your amount of strength and magic damage is augmented by your amount of intelligence. That's why weapons with higher magic damage are better for mage type characters because they typically have higher intelligence.
So is it possible to kill Amdusias in Nightmare mode? Yes, I've done it myself, but it took me a good few tries.
His most deadly attack is his stun + explosive arrow(s) combo, so rush attacking him before he has a chance to fire those is actually a pretty good strategy. If you had resisted his fear spell you might well have ended up winning the fight – given you had a more than healthy supply of rejuvenation potions and your creature to back you up.
