Tight constraints on the abundance of primordial black holes can be deduced across a vast range of masses, with the exception of those light enough to fully evaporate before nucleosynthesis. This hypothetical population is almost entirely unconstrained, to the point where the early Universe could pass through a matter-dominated phase with primordial black holes as the primary component. The only obvious relic of this phase would be Hawking radiated gravitons which would constitute a stochastic gravitational wave background in the present-day Universe, albeit at frequencies far beyond the scope of any planned detector technology. This paper explores the effects of classical mergers in such a matter dominated phase. For certain ranges of parameters, a significant fraction of the black holes merge, providing an additional, classical source of primordial gravitational waves. The resulting stochastic background typically has a lower amplitude than the Hawking background and lies at less extreme frequencies, but is unlikely to be easily detectable, with a maximal present day density of $\Omega_{GW} \sim 10^{-12}$ and frequencies between $10^{15} - 10^{19}$ Hz. We also asses the impact of radiation accretion on the lifetimes of such primordial black holes and find that it increases the black hole mass by $\sim 14 \%$ and the lifetimes by about $50 \%$. However, this does not qualitatively change any of our conclusions.