Abrupt fluid emissions from shallow marine sediments pose a threat to seafloor installations like wind farms and offshore cables. Quantifying such fluid emissions and linking pockmarks, the seafloor manifestations of fluid escape, to flow in the sub-seafloor remains notoriously difficult due to an incomplete understanding of the underlying physical processes. Here, using a compositional multi-phase flow model, we test plausible gas sources for pockmarks in the south-eastern North Sea, which recent observations suggest have formed in response to major storms. We find that the presence of free gas in the subsurface effectively damps storm wave-induced pressure changes due to its high compressibility, so that the mobilization of pre-existing gas pockets is unlikely. Rather, our results point to spontaneous appearance of a free gas phase via storm-induced gas exsolution from pore fluids. This mechanism is primarily driven by the pressure-sensitivity of gas solubility. We show that in highly permeable sediments containing gas-rich pore fluids, wave-induced pressure changes result in the appearance of a persistent gas phase. This suggests that seafloor fluid escape structures are not always proxies for overpressured shallow gas and that periodic seafloor pressure changes can induce persistent free gas phase to spontaneously appear.