Aims: We aim to develop an efficient method to search for late-type subdwarfs (metal-depleted dwarfs with spectral types ≥M5) to improve the current statistics. Our objectives are to improve our knowledge of metal-poor low-mass dwarfs, bridge the gap between the late-M and L types, determine their surface density, and understand the impact of metallicity on the stellar and substellar mass function. Methods: We carried out a search cross-matching the Sloan Digital Sky Survey (SDSS) Data Release 7 (DR7) and the Two Micron All Sky Survey (2MASS), and different releases of SDSS and the United Kingdom InfraRed Telescope (UKIRT) Infrared Deep Sky Survey (UKIDSS) using STILTS, Aladin, and Topcat developed as part of the Virtual Observatory tools. We considered different photometric and proper motion criteria for our selection. We identified 29 and 71 late-type subdwarf candidates in each cross-correlation over 8826 and 3679 sq. deg, respectively (2312 sq. deg overlap). We obtained our own low-resolution optical spectra for 71 of our candidates: 26 were observed with the Gran Telescopio de Canarias (GTC; R 350, λλ5000-10 000 Å), six with the Nordic Optical Telescope (NOT; R 450, λλ5000-10 700 Å), and 39 with the Very Large Telescope (VLT; R 350, λλ6000-11 000 Å). We also retrieved spectra for 30 of our candidates from the SDSS spectroscopic database (R 2000 and λλ 3800-9400 Å), nine of these 30 candidates with an independent spectrum in our follow-up. We classified 92 candidates based on 101 optical spectra using two methods: spectral indices and comparison with templates of known subdwarfs. Results: We developed an efficient photometric and proper motion search methodology to identify metal-poor M dwarfs. We confirmed 86% and 94% of the candidates as late-type subdwarfs from the SDSS vs. 2MASS and SDSS vs. UKIDSS cross-matches, respectively. These subdwarfs have spectral types ranging between M5 and L0.5 and SDSS magnitudes in the r = 19.4-23.3 mag range. Our new late-type M discoveries include 49 subdwarfs, 25 extreme subdwarfs, six ultrasubdwarfs, one subdwarf/extreme subdwarf, and two dwarfs/subdwarfs. In addition, we discovered three early-L subdwarfs to add to the current compendium of L-type subdwarfs known to date. We doubled the numbers of cool subdwarfs (11 new from SDSS vs. 2MASS and 50 new from SDSS vs. UKIDSS). We derived a surface density of late-type subdwarfs of 0.040 per square degree in the SDSS DR7 vs. UKIDSS LAS DR10 cross-match (J = 15.9-18.8 mag) after correcting for incompleteness. The density of M dwarfs decreases with decreasing metallicity. We also checked the Wide Field Survey Explorer (AllWISE) photometry of known and new subdwarfs and found that mid-infrared colours of M subdwarfs do not appear to differ from their solar-metallicity counterparts of similar spectral types. However, the near-to-mid-infrared colours J-W2 and J-W1 are bluer for lower metallicity dwarfs, results that may be used as a criterion to look for late-type subdwarfs in future searches. Based on observations made with ESO Telescopes at the La Silla Paranal Observatory under programmes IDs 088.C-0250(A), 090.C-0832(A).Based on observations made with the Nordic Optical Telescope, operated by the Nordic Optical Telescope Scientific Association at the Observatorio del Roque de los Muchachos, La Palma, Spain, of the Instituto de Astrofísica de Canarias.Based on observations made with the Gran Telescopio Canarias (GTC), installed in the Spanish Observatorio del Roque de los Muchachos of the Instituto de Astrofísica de Canarias, in the island of La Palma (programs GTC44-09B, GTC53-10B, GTC31-MULTIPLE-11B, GTC36/12B, and GTC79-14A).The data presented in this paper are gathered in a VO-compliant archive at http://svo2.cab.inta-csic.es/vocats/ltsa/The photometric and spectroscopic data are available at the CDS via anonymous ftp to http://cdsarc.u-strasbg.fr (http://130.79.128.5) or via http://cdsarc.u-strasbg.fr/viz-bin/qcat?J/A+A/598/A92