Context. Tracing the molecular gas-phase in low-mass star-forming galaxies becomes extremely challenging due to significant UV photo-dissociation of CO molecules in their low-dust, low-metallicity ISM environments. Aims: We aim to study the molecular content and the star-formation efficiency of a representative sample of 21 blue compact dwarf galaxies (BCDs), previously characterized on the basis of their spectrophotometric properties. Methods: We present CO (1-0) and (2-1) observations conducted at the IRAM-30m telescope. These data are further supplemented with additional CO measurements and multiwavelength ancillary data from the literature. We explore correlations between the derived CO luminosities and several galaxy-averaged properties. Results: We detect CO emission in seven out of ten BCDs observed. For two galaxies these are the first CO detections reported so far. We find the molecular content traced by CO to be correlated with the stellar and Hi masses, star formation rate (SFR) tracers, the projected size of the starburst, and its gas-phase metallicity. BCDs appear to be systematically offset from the Schmidt-Kennicutt (SK) law, showing lower average gas surface densities for a given ΣSFR, and therefore showing extremely low (≲0.1 Gyr) H2 and H2 +Hi depletion timescales. The departure from the SK law is smaller when considering H2 +Hi rather than H2 only, and is larger for BCDs with lower metallicity and higher specific SFR. Thus, the molecular fraction (ΣH2/ ΣHI) and CO depletion timescale (ΣH2/ ΣSFR) of BCDs is found to be strongly correlated with metallicity. Using this, and assuming that the empirical correlation found between the specific SFR and galaxy-averaged H2 depletion timescale of more metal-rich galaxies extends to lower masses, we derive a metallicity-dependent CO-to-H2 conversion factor αCO,Z ∝ (Z/Z⊙)- y, with y = 1.5(±0.3)in qualitative agreement with previous determinations, dust-based measurements, and recent model predictions. Consequently, our results suggest that in vigorously star-forming dwarfs the fraction of H2 traced by CO decreases by a factor of about 40 from Z ~ Z⊙ to Z ~ 0.1 Z⊙, leading to a strong underestimation of the H2 mass in metal-poor systems when a Galactic αCO,MW is considered. Adopting our metallicity-dependent conversion factor αCO,Z we find that departures from the SK law are partially resolved. Conclusions: Our results suggest that starbursting dwarfs have shorter depletion gas timescales and lower molecular fractions compared to normal late-type disc galaxies, even accounting for the molecular gas not traced by CO emission in metal-poor environments, raising additional constraints to model predictions. Based on observations carried out with the IRAM 30m Telescope. IRAM is supported by INSU/CNRS (France), MPG (Germany) and IGN (Spain).