When Lanfear and Graendal start staring each other down, Rahvin is prepared to Travel if he senses even a "whiff of balefire." Plainly it is detectable by its effects, regardless of what power is used to generate it. For example, fire or lightning have characteristics even non-channelers can detect, such as heat and light, though admittedly not before they are created. And since they can strike into the Guardian and can hurt Mat with his medallion, they are obviously real fire and lightning, not constructs of saidar or saidin. The weave is used to genertate them, to get them started. Presumably balefire is something similar - it is started and controlled by the weaves, but has its own characteristics and is not solely a construct of the Power, like Rand's fire sword, or an illusion. Is it such a stretch that a temporal-natured energy like balefire can be felt before it is woven, especially since it kills people before it was woven?