The mercenaries in question are all from the same species, have technology comparable to that of the human clients (us) but place little, if any value in human currency. By comparable I mean their tech is as advanced as ours, however it's too incompatible to barter for equipment, spare parts or fuel. Also due to their biology and preferred habitat (in this particular example I imagined an amphibious species capable of periods on dry land but eventually must return to an underwater habitat, if this helps any) trading medicines or foodstuffs probably would be out as well. What would we (or another species in hostilities against us) have to offer them?
Surprisingly there is in fact already real theory about interstellar trade.
An important point is that you would expect arbitrage between the 2 planets as long as there is something, anything, anything at all that the 2 want to trade.
Once there's arbitrage you should be able to pay for services with simple money, either your own or theirs though probably at a steep exchange rate.
As long as someone else is trading something, it could be some kind of raw material or rare metal, information like industrial methods or material science or services like humans performing some service. Perhaps they sometimes need to hire human mercenaries for desert warfare.
The important thing to remember is that your protagonists don't need to find that rare metal, find the industrial methods or act as mercenaries themselves as long as some humans from their own planet are already doing that in exchange for something because at that point someone else will be trying to make money off interstellar arbitrage. Perhaps your aliens use crystals for money, doesn't matter. You'd be able to go to a human finance firms and swap Terran Union Credit Chips or whatever currency they use for the alien currency. Though almost certainly at an extortionate exchange rate.
In terms of practical things humans could provide my first thought is that humans can operate pretty comfortably in deserts. I'm assuming low-scifi tech, think our tech level with spaceships, lasers and amazing gadgets but no nanotech or autonomous robots or infinite energy machines so that labor is still of value.
Energy is pretty a pretty universal need for civilization. If their world has any deserts then they're going to be very very harsh on an amphibious species. Humans could set up deep in the middle of their version of the Sahara and build massive solar farms selling power to the frogs. I could imagine some of the aliens leasing areas of the ocean on human planets and farming/managing/mining the ocean depths where it's too too dark and too hostile for humans.
We would trade them things they want.
This seems like a duh, because it is. As the story writer, it is your job to decide what it is they want. Technically, your question is off-topic because it's an idea-generating question, but I'll answer a slightly different question: "how do I determine what it is they would want for trading, given limitations X, Y, and Z?"
There are two things to trade: goods and services.
I suspect that some of the mercenaries will be collectors, happy to trade for "worthless" trinkets which are neat. By and large though I don't expect this to be the case.
So you're left with services: things you can do for them.
If they eventually need to return to water, then they would be somewhat ineffective in space where water isn't particularly prevailiant. At some point, something's going to happen and they will all need to be back in water. What if they had somebody without that limitation to help them keep the ship in one piece while they're doing that?
What if they trained somebody who could look after their non-aquatic ships and perform maintenance. Yes, their technology is different, but you could still learn to work with it. Furthermore, there may be some tasks which require hours of continuous monitoring - so they'd either have to work in shifts or have a non-aquatic person watch it.
You could also learn to build things they need, thereby enabling yourselves to trade goods like you're used to.
Anyway, there are some ideas - but the real answer is to continue thinking down this line of thought asking yourselves what kinds of things can you write into the world that they would want?
Something with intrinsic value that is also fungible and quantifiable. For beings across the universe, that will probably be energy.
Mercenaries will need energy to run their spacecraft, power their weapons, supply the life support systems they use and so on. Anyone to anything they meet and interact with will also need energy in some form or other of do the things they want to do, so the mercenaries will need to have energy in a form which is rather compact and easily transferrable.
What that form actually is is up to you. Batteries carry electrochemical energy in a fairly dilute form (which is why electric cars were displaced over a century ago and are not making a comeback regardless of what Elon Musk or GM say), but electrochemical energy is much denser and more easily handled in hydrocarbon form. Having alien mercenaries being paid in coal or oil is strange to contemplate, but quite sensible since hydrocarbons have energy densities 20-50X greater than battery technology.
Order of magnitude higher energy densities are possible with nuclear energy, so you might pay your mercenaries with Uranium of Plutonium, or if they have mastered fusion energy, tank up their ships with D2 or 3He. If you are minting coins out of fissile material, encourage the mercenaries to use lead wallets and not to carry lots of change.....
The highest possible energy density storage is antimatter. Assuming you have a reasonable means of either making or harvesting antimatter, you can provide energy in the most compact possible form (canisters of frozen anti hydrogen is possible with currently known technology, although we don't have enough anti hydrogen to really make this worth while). The issue right now is antimatter is made at such low efficiencies that we would go bankrupt trying to supply any reasonable amount to the mercenaries, and our current technology isn't up to long term storage or bulk supply handling of antimatter in the sorts of amounts that an interstellar mercenary band might want. Still, there is incentive to work on both antimatter production and storage technologies for our own use, and that might translate in the future as a means of interstellar payments.
- Sanctuary for their rear area troops, protected by our frontline troops. The fact that they're amphibian might help, offer them some nice tropical islands with the surrounding seabed. The deal is that they'd be under our SAM umbrella from the mainland and that they will patrol the waters.
- Spare parts made by us to their specifications. They might not use metric fittings, but we can start a production line just for them.
- Same for medicines. They give us a sample, we replicate it.
Yes, you read it right. We can offer ourselves (or humans that we believe are inferior) to that alien race, and even an enemy race can offer our people to the mercenary race. Why an alien race would need slaves? Let's examine two real cases: the Viking/Spartans slave system and the Atlantic slave trade
Viking/Spartan mode - We need to support a neverending war machine
You said that your amphibious race is a race of mercenary, didn't you? So, I guess that they hold in high esteem the maintaining of their military equipment, and training of all able-bodied men. The problem is that war is something extremely costly, not only in terms of lives, but also of time, energy and resources. So, how do you devote yourself to war, if there is no one who cultivates fields? The answer is: someone who does not participate to war, and don't use so many resources. The slave is perfect for this role. The Vikings had a polygamous society and perpetually devoted to war. So slavery was a very significant motivator in raiding. They captured women for themselves, men to work in the fields and to manufacture the tools that warriors would use. Even the Spartan economy was based on enslavement of an entire population, the Helots. The Spartans were fighting, and the Helots had to support them with their work.
Atlantic slave trade mode - We have resources, we have no manpower
Imagine finding a planet where there is already a native breed. The planet is very rich in natural resources, and you, the galactic conqueror, enslave the population to extract resources. Only the native race is weak. It is not used for forced labor. So you always have the same problem: how to exploit these resources if workers die? Discover by chance another race, whose people are in constant conflict with each other for trivial reasons, but they are physically stronger than the native breed. So you decide to take advantage of these reasons, and to enslave the enemy of a population of this race. You have your strong workers, and have them free.
Now I imagine a situation where your race of mercenaries is not as belligerent as in the previous case. Perhaps the planet is rich in resources, but given the amphibious nature of your race, it is difficult to fully exploit them. Instead humans are adaptable. They always have been, it is one of their characteristics. Here they serve. Slaves can handle the extraction of native resources when amphibians can not.
However, the use of slaves presupposes some requirements. Meanwhile, the labor force must be very economic. In our world, to use slaves rather than paid workers in the Third World is profitable because it is REALLY profitable. In the 800 cultures this distinction was not so clear, and that is why Adam Smith wrote that it was better to pay a worker rather than exploit it.
There's no telling what their biology is. It would be likely that any human medicine would have no value to them whatsoever, outside of studying it. This would mean it would have no trade value. The same goes for their technology: who knows what they use as fuel.
So as far as trade value goes, the following would seem feasable:
- Conductive materials: it is highly likely their technology needs conductivity, so conductive materials (copper, gold and graphite) could have a reliable trade value
- Precious metals: titanium, gold and silver could have industrial use even to them.
- Crystals: diamonds, graphite (also conductive) and other crystals could have value for their technology.
Other than these functional trade items, human weaponry (possibly modified to be usable by alien bodies), human art and some commodities such as art could have value, but for real trade it would probably be limited to any functional recourses their planet might lack.
There are going to be two stages to trade.
In the first stage you can pay them in
Just about anything manufactured
The novelty gives things value. A plastic model of a horse will be such an unusual item, such a strange alien creature than it will have, for a time, value on alien markets. Even photos of Earth, white clouds? a blue sky? way out man! Later as the market starts to saturate you'll have out actual animals for a while. Everybody loves invasive alien species on the black market.
Eventually these things will lose their value as the novelty wears off and you end up needing something a bit different.
Works of art
These will probably turn out to be the ultimate in transferable trade goods on the interplanetary market. Art remains unique and special to a planet even if fairly basic, as it does for the various regions on Earth. Against a vast galactic population, works of art in a specific planetary style will always remain in limited supply.
Your problem is mass.
Stuff like metals or anything manufactured is going to be heavy - meaning fuel. So you're after things that are rare or unique to your host civilization. They'll want fuel anyway - but they may have seeded your local gas giant with He3 refinery seeds on the way in - so you may not have that to sell.
Information may be useful - but I can't see our science or maths being anything they wouldn't have already got.
Psychology or Biology on the other hand could be valuable as science. Its possible we might have bacteria that might have industrial applications (e.g. metal extraction, specific fermentation products) that they might have use for - Bacteria aren't affected by the weight problem because they can replicate and be frozen pretty readily. But its likely that they already have that already either by microbiology or artificial nanotechnology.
So its going to be art or music or fiction. All of which may not have any aesthetic value to an alien at all (but they could sell onto collectors or other races). Your aliens might like dolphin brain wave patterns, their art may not be understandable by us at all.