We have assembled a multifrequency data base by cross-correlating the NRAO VLA Sky Survey (NVSS) catalogue of radio sources with the RASSBSC list of soft X-ray sources, obtaining optical magnitude estimates from the Palomar and UK Schmidt surveys as provided by the Automated Plate Measurement (APM) and COSMOS on-line services. By exploiting the nearly unique broad-band properties of high-energy peaked BL Lacs (HBL), we have statistically identified a sample of 218 objects that is expected to include about 85 per cent of BL Lacs and that is therefore several times larger than all other published samples of HBLs. Using a subset (155 objects) that is radio-flux-limited and statistically well-defined, we have derived the VVm distribution and the log N-log S of extreme HBLs (f(x)f(r) greater than or equal to 3 x 10(-10) erg cm(-2) s(-1) Jy(-1)) down to 3.5 mJy. We find that the log N-log S flattens around 20 mJy and that [VVm] = 0.42 +/- 0.02. This extends to the radio band earlier results, based on much smaller X-ray-selected samples, about the anomalous cosmological observational properties of HBLs. A comparison with the expected radio log N-log S of all BL Lacs (based on a beaming model) shows that extreme HBLs make up roughly 2 per cent of the BL Lac population, independently of radio flux. This result, together with the flatness of the radio log N-log S at low fluxes, is in contrast with the predictions of a recent model that assumes an anticorrelation between peak frequency and bolometric luminosity. This scenario would in fact result in an increasing dominance of HBLs at lower radio fluxes; an effect that, if at all present, must start at fluxes fainter than our survey limit. The extreme f(x)f(r) flux ratios and high X-ray fluxes of these BL Lacs makes them good candidate TeV sources; some of the brighter (and closer) ones are possibly detectable with the current generation of Cerenkov telescopes. Statistical identification of sources based on their location in multiparameter space, of the kind described here, will have to become commonplace with the advent of the many large, deep surveys at various frequencies currently scheduled or under construction.