This really depends on how you are authenticating with the GitHub Enterprise repository and what remote type you are using.
If you are using the GitHub remote this will likely only work if the GitHub host of the Remote matches that of the main repository, e.g. I don't think there is a way to have the main package live on normal GitHub, and the remote package live on the GHE instance. If they both live on the same GHE instance than it should work provided you supply the host to devtools::install_github().
An alternative would be to use the Git remote. In this case you would need to provide the necessary credentials to either command line git via ssh or to git2r with the credentials = argument.
A third alternative would be to use the url remote and give the location of the zipball / tarball for the GHE repository. This would only require you to have access to that URL in some way.
Unfortunately when we designed the Remotes field we decided not to provide support for passing additional arguments to the remotes, which makes these types of issues tricky.
For a travis build in this situation I think the best solution would be to not use the Remotes field, and instead call the appropriate install_*() function separately in a before_script step. e.g.
before_script: R -e 'devtools::install_github("foo/bar", host = "github.mycompany.com/api/v3")