We obtain sharp upper and lower bounds on a certain four-dimensional Frobenius number determined by a prime pair (p, q), 2 < p < q, including exact formulae for two infinite subclasses of such pairs. Our work is motivated by the study of compact Riemann surfaces which can be realised as semi-regular pq-fold coverings of surfaces of lower genus. In this context, the Frobenius number is (up to an additive translation) the largest genus in which no surface is such a covering. In many cases it is also the largest genus in which no surface admits an automorphism of order pq. The general t-dimensional Frobenius problem (t ≥ 3) is NP-hard, and it may be that our restricted problem retains this property.