I can only assume that this would be because a new connection is initiated every time. That is, every open and opendir is connecting anew to the remote server. I am not sure what to do about this, if there is anything. Have you tried accessing files on your own (with perl, of course) and benchmarked that (so you know if it is File::Find or perl that has a hard time with windows shares).

Also, I could think to try and toggle no_chdir in File::Find although I don't really expect any great effect from that, it is worth a shot. Maybe that affects how connections are made.