The Kennicutt-Schmidt (KS) relation between the gas mass and star formation rate (SFR) describes the star formation regulation in disk galaxies. It is a function of gas metallicity, but the low metallicity regime of the KS diagram is poorly sampled. We have analyzed data for a representative set of extremely metal-poor galaxies (XMPs), as well as auxiliary data, and compared these to empirical and theoretical predictions. The majority of the XMPs possess high specific SFRs, similar to high redshift star-forming galaxies. On the KS plot, the XMP HI data occupy the same region as dwarfs, and extend the relation for low surface brightness galaxies. Considering the HI gas alone, a considerable fraction of the XMPs already fall off the KS law. Significant quantities of 'dark' H$_2$ mass (i.e., not traced by CO) would imply that XMPs possess low star formation efficiencies (SFE$_{\rm gas}$). Low SFE$_{\rm gas}$ in XMPs may be the result of the metal-poor nature of the HI gas. Alternatively, the HI reservoir may be largely inert, the star formation being dominated by cosmological accretion. Time lags between gas accretion and star formation may also reduce the apparent SFE$_{\rm gas}$, as may galaxy winds, which can expel most of the gas into the intergalactic medium. Hence, on global scales, XMPs could be HI-dominated, high specific SFR ($\gtrsim $ 10$^{-10}$~yr$^{-1}$), low SFE$_{\rm gas}$ ($\lesssim$ 10$^{-9}$~yr$^{-1}$) systems, in which the total HI mass is likely not a good predictor of the total H$_2$ mass nor of the SFR.