I've not seen "Fairy Tale", but something on the same lines, with (I think) Paul McGann in.

Paul McGann is in FairyTale; he plays the father of one of the girls (the uncle of the other), Arthur Wright, the engineer. You might also have seen Photographing Fairies, though, in which case you should read this article.

It's not something I could watch again, but some twist in my head insists on it looking rather like a Brothers Quay animation. Which would be truly nasty.

There is stop-motion. It's a striking effect.