We report on the discovery of four ultra-short period (P<0.18 days) eclipsing M-dwarf binaries in the WFCAM Transit Survey. Their orbital periods are significantly shorter than of any other known main-sequence binary system, and are all significantly below the sharp period cut-off at P~0.22 days as seen in binaries of earlier type stars. The shortest-period binary consists of two M4 type stars in a P=0.112 day orbit. The binaries are discovered as part of an extensive search for short-period eclipsing systems in over 260,000 stellar lightcurves, including over 10,000 M-dwarfs down to J=18 mag, yielding 25 binaries with P<0.23 days. In a popular paradigm, the evolution of short period binaries of cool main-sequence stars is driven by loss of angular momentum through magnetised winds. In this scheme, the observed P~0.22 day period cut-off is explained as being due to timescales that are too long for lower-mass binaries to decay into tighter orbits. Our discovery of low-mass binaries with significantly shorter orbits implies that either these timescales have been overestimated for M-dwarfs, e.g. due to a higher effective magnetic activity, or that the mechanism for forming these tight M-dwarf binaries is different from that of earlier type main-sequence stars.