  The "defect" of a curve over a finite field is the difference between the
number of rational points on the curve and the Weil-Serre bound for the curve.
We present a construction for producing genus-4 double covers of genus-2 curves
over finite fields such that the defect of the double cover is not much more
than the defect of the genus-2 curve. We give an algorithm that uses this
construction to produce genus-4 curves with small defect. Heuristically, for
all sufficiently large primes and for almost all prime powers q, the algorithm
is expected to produce a genus-4 curve over F_q with defect at most 4 in time
q^{3/4}, up to logarithmic factors.
  As part of the analysis of the algorithm, we present a reinterpretation of
results of Hayashida on the number of genus-2 curves whose Jacobians are
isomorphic to the square of a given elliptic curve with complex multiplication
by a maximal order. We show that a category of principal polarizations on the
square of such an elliptic curve is equivalent to a category of right ideals in
a certain quaternion order.
