An often used trick to transfer entire file trees is packing them. See CPAN. Lotsa *tar.gz files there.

If that's not feasible, you'd need to create the directories on the remote site first, then transfer the files. If Net::SFTP::Recursive doesn't do that, you could still issue mkdir -p via ssh.