Also be very sure you are killing the right types. There’s several versions and the quest probably requires a specific type.
I do remember it took me quite long too though. It reminded me of the Zhevra hooves quest on Vanilla, but those I got in no time in Classic. Maybe they switched places,