Hard Counter to Opponent's Strength: Blindsight
OP says that he is most interested in ways to negate the effect of the paladin's fog. As smbailey's answer points out, the hard counter to non-magical fog is blindsight. Unfortunately, nearly everything that grants blindsight does so to such a limited distance that it is unlikely to be helpful except in melee, and if your plan involves melee, will you be taking on all of the paladin's group by yourself? Or, if you are bringing allies, can you provide each of them with blindsight?
Blind Fighting Fighting Style will get you blindsight to 10 feet, as will the Ascendant Aspect of the Way of the Ascendant Dragon Monk. A ranger's Feral Senses will counter the fog to 30', as will the Draconic Transformation spell or the unique magic item Dagger of Blindsight. However, even 30' is awfully short unless you can equip your whole group. Between them, the Hoard of the Dragon Queen and the Rise of Tiamat contain five magic items that will grant blindsight to 30' for five minutes a day.
Each of the five Dragon Masks have this ability. Even if your characters play the adventures, they are unlikely to gain access to more than one of the masks, at least until the very end, when they have a chance to capture the combined five. However, if this adventure series has already happened, or has not happened yet, in the timeline of your campaign, it might be possible to obtain one or more of the masks, either before or after they are important.
Besides items, you might acquire blindsight by tapping into the senses of a familiar (find familiar) or animal companion (beast sense). Some suggested forms that naturally have blindsight would be bats, crabs, and psuedodragons. Unfortunately, seeing through the eyes of the beast or beast form requires your action, meaning there is little you can do to capitalize on not being blinded by the fog. Alternately, you could wild shape, shapechange, or polymorph into a form with blindsight (bat, crab, giant crab, giant constrictor snake). In this case you would preserve your action, but the possible uses of your action in that form are underwhelming. Overkill would be, as a 20th level wizard or druid, true polymorphing or shapechanging yourself into an ancient brass dragon. Then you would have natural, actionless blindsight to 60 feet and a host of offensive options. But if you are a 20th level full caster it seems an odd choice to be focused on countering your opponent's fog compared to your other options for dealing with them.
Soft counter to Opponent's Strength: Offsetting Advantage
As Ryan C. Thompson's answer says, area of effect spells typically don't care about whether you can see the secondary targets or not. The fog tells you where the targets are, so blast away! However, OP desires something more sophisticated.
The paladin's mobile fog screen protects them and their allies - you can't see them, so you are at disadvantage in all your attacks. However, you do know where the paladin is - they are in whichever square is at the center of the fog. And if the paladin's allies are within 5' of them, there are only eight squares in which they can be - so the more allies, the more likely you can guess one of their squares as well. You don't have to see them to attack - you just declare the square you think, or know, they are in. You do have disadvantage on the attack - unless you can find some way to also have advantage, in which case they offset and you have a flat roll, which is a soft counter to the fog. There are lots of ways to gain advantage, and many of them work even against opponents you cannot see. Consult here and here for some examples, but especially consider an invisible flying familiar with the Help action. Remember also that if they can't see you, it doesn't matter that you can't see them, so there is another way to offset the disadvantage (and see mirror match, below).
If you are primarily engaging them with missile weapons, this soft counter may be enough to achieve your objective of continuing to effectively target the paladin. However, the OP says that he wants to target the opponents with spells that work on line of sight, and many spells require you to see the target. If those spells are your principal offense, the soft counter of offsetting advantage will be insufficient.
Soft counter to Opponent's Strength: Forced Movement
Your opponent is using the fog to protect their group from attacks that rely on sight. They can only do that, however, by keeping them in a tight cluster within twenty feet of the paladin, and much of the protection is lost at more than five feet from the paladin. So one counter strategy is forced movement. If you can get the paladin to flee, all of their group will be exposed. If you can get the group to scatter, you can focus fire on the weaker opponents. One option is fear, although at third level and 30' range it's not great. Paladins aren't immune to fear until 10th level. If you have access to a wand of fear, no spell slots and a 60 foot range is pretty decent1. At a lower level is the bard's dissonant whispers. Eminently repeatable and a 60 foot range; the target has to be able to hear you but you don't have to be able to see it. If your warlock is of high enough level to get two eldritch blasts per turn, then repelling blast might be enough to push one of your opponents out of the fog, or force the paladin back far enough to reveal his allies. No save, but you do have to hit and you will likely be firing with disadvantage. Still, 120' range2.
Exploiting the Opponent's Weakness: Poor Maneuverability
Up until now I have been making a good faith effort to address OP's stated goal of countering the fog by negating it. However, rather than trying to counter the opponent's strength, in this case it is far more practical to exploit their weakness, which is their poor maneuverability.
In the real world, infantry are trained to move in formation, whether that is for rapidly covering long distances (marching) or for engaging enemies as units (at tactical speed). The 5e ruleset, however, with its initiative order and turn-based movement makes the latter particularly difficult to do. If the paladin is stationary, the counter to the fog is to just retreat out of range or behind cover and wait out the duration of the Marine Layer. But if the paladin tries to move, consider the problems that poses to them and their allies. As soon as the paladin moves more than five feet, most of their allies are no longer within five feet of them and are thus blinded, meaning your attacks on them are no longer at disadvantage. If the paladin moves more than twenty feet, their allies will likely be left out of the fog and will become prime targets, at least until their own turn for movement. Your group can focus attacks on theses opponents exposed and left behind. To get around this, the paladin might creep along, keeping their group protected, but at the cost of movement rate. Or, the entire group might ready actions to move in formation on the paladin's turn, but at a cost of giving up their own on-turn actions and crippling their offensive capability.
If your group counters the fog by being mobile and staying out of range, the paladin's group is already at a tactical disadvantage. But you can do more than that. There are a wealth of spells that impose difficult terrain (for example web, entangle, and spike growth) that you can drop in front of the fog to further slow the paladin's progress. These are typically low-level spells, allowing them to be cast repeatedly, and they usually have good range. Their add-on effects might include damage or restraining. The more allies the paladin has, the more likely one of them will fail its save (even given that paladin's frustrating aura of protection). If you can restrain just one of the paladin's allies, their group then has a devil's choice of stopping until the ally is freed, or continuing on without them, meaning that the ally left behind is not only exposed but can be attacked at advantage once their group has moved on.
Basically this is the strategy of 'kiting' your opponent, but your goals, in addition to doing ranged damage and denying them the ability to close, is to force them to split up and then to attack the members of their group that are no longer protected, as well as running out the clock on the fog.
The Mirror Match: Poor Spectacle
If your group doesn't have the mobility and range attacks you would need to effectively kite the paladin's group, you might consider the mirror strategy; covering your own group in a way that makes it more difficult to target, typically by casting darkness on an object one of you carries (I suggest something carried by your warlock with devil's sight). Your group will be subject to the same difficulties in moving that the paladin's group has, but you will be equally protected. If you think you can win a melee with a level playing field, you might then just charge in, trusting that no one in the combat can see anyone else. Or, you can continue to circle them at a distance, protected from their ranged attacks but denying them contact until the fog times out.
OP has said that this contest might be part of a tournament arc. In such a case, it is likely that the spectators and judges will not be happy that the combat is unwatchable, or that you are deliberately frustrating the action tempo they expect. Sometimes, however, your lives are worth more than your fortunes or honor.
1And if you have access to an imp familiar and a wand of fear, why haven't you had the imp attune to the wand yet?
2Can your team hire a ringer for the length of the tournament? You are looking for a pact of the chain warlock with an imp familiar, wand of fear, eldritch blast on tap, both repelling blast and eldritch spear invocations, darkness, and devil's sight. They can stay at 300 feet from the fog and blast opponents out of it with impunity. The rest of your team just does what you normally do and focus fire on the opponents as they get tossed out of the fog.
