Locating ultra-cool companions to M dwarfs is important for constraining low-mass formation models, the measurement of sub-stellar dynamical masses and radii, and for testing ultra-cool evolutionary models. We present an optimised method for identifying M dwarfs which may have unresolved ultra-cool companions. We construct a catalogue of 440,694 candidates, from WISE, 2MASS and SDSS, based on optical and near-infrared colours and reduced proper motion. With strict reddening, photometric and quality constraints we isolate a sub-sample of 36,898 M dwarfs and search for possible mid-infrared M dwarf + ultra-cool dwarf candidates by comparing M dwarfs which have similar optical/near-infrared colours (chosen for their sensitivity to effective temperature and metallicity). We present 1,082 M dwarf + ultra-cool dwarf candidates for follow-up. Using simulated ultra-cool dwarf companions to M dwarfs, we estimate that the occurrence of unresolved ultra-cool companions amongst our M dwarf + ultra-cool dwarf candidates should be at least four times the average for our full M dwarf catalogue. We discuss possible contamination and bias and predict yields of candidates based on our simulations.