Will this RouteFinder work over frame relay?

You can't put it directly on a frame relay line, but you can plug it into a router that supports frame relay and provides a ethernet connection.