I think you must mean this man with an Americanized last name. He had already been to the U.S., so his Swedish parish is not listed on Emihamn. There is no listing on this cd telling ship names, by the way.
Efternamn (last name): MARTINS
Förnamn (given name): VICTOR
Ålder (age): 31 Kön (gender): M
Född (born): 1867/1868
Församling (parish: not named since he lived in the U.S. and had just returned to Sweden for a visit.): AMERIKA Län (county): US
Titel/Anm (title/remarks):
Utresehamn (moving out port): GÖTEBORG (Gothenburg)
Utvandrdag (moving out day): 1899 02 08 (8 February)
Destination (destination): NEW YORK
Medåkande (traveled with): NEJ (no)
Källkod (source code): 63:95:1325 (volume: page: ticket number)
I think that the world version of Ancestry.com has the "poliskammare" (harbor police) records. SVAR (a subscription site) does too and maybe Arkiv Digital (another subscription site) does also. These records will show the feeder ship taking the passengers to Hull or Grimsby in England, where they got on a train to cross to an English port such as Liverpool and Southampton to continue on a larger ship to cross the ocean.
A FAR more active board such as the following could have given you an answer almost immediately. This board is very inactive in comparison and most of us don't know about it or forget about it.
http://boards.rootsweb.com/localities.scan-balt.sweden.gener...Judy