I read a fantasy book as a youth that I cannot for the life if me remember the title to. It's all rather fuzzy except one particular scene and detail. I'll list what I can remember.
It's a female protagonist, I believe of the unlikely hero/questing type. There are forest-dwelling creatures abundant in this universe that assume the guise of something comforting or appealing to whoever sees them to lure them to their deaths.
The wizard/mage she encounters doesn't walk on the earth, and instead floats just above the ground, leaving no footprints. The mage is the romantic interest. There is a scene between the two where she believes him to be one of the aforementioned creatures because he lacks footprints.
I know it's not much to go on, but I've searched high and low to no avail. It's doing my head in trying to remember. Any help would be much appreciated.
