We present a search for RR Lyrae variable stars from archival observations of the Southern Edgeworth-Kuiper Belt Object survey. The survey covers 1675 square degrees along the ecliptic to a mean depth of V=19.5, i.e. a heliocentric distance of ~50kpc for RR Lyrae stars. The survey reveals 2016 RR Lyrae candidates. Follow-up photometric monitoring of a subset of these candidates shows (24+/-12)% contamination by non-RR Lyrae variables. We derive a map of over-density of RR Lyraes in the halo that reveals a series of structures coincident with the leading and trailing arms of debris from the Sagittarius dwarf galaxy. One of the regions of over-density is found on the trailing arm, 200 deg. from the main body of the Sagittarius dwarf at a distance of ~45kpc. This distant detection of the stellar population of the outer trailing arm of Sagittarius offers a tight constraint on the motion of the dwarf galaxy. A distinctly separate region of over-density is seen towards the Virgo Over Density.