We experimentally demonstrate a new regime of high-order harmonic generation by relativistic-irradiance lasers in gas jet targets. Bright harmonics with both odd and even orders, generated by linearly as well as circularly polarized pulses, are emitted in the forward direction, while the base harmonic frequency is downshifted. A 9 TW laser generates harmonics up to 360 eV, within the 'water window' spectral region. With a 120 TW laser producing 40 uJ/sr per harmonic at 120 eV, we demonstrate the photon number scalability. The observed harmonics cannot be explained by previously suggested scenarios. A novel high-order harmonics generation mechanism [T. Zh. Esirkepov et al., AIP Proceedings, this volume], which explains our experimental findings, is based on the phenomena inherent in the relativistic laser - underdense plasma interactions (self-focusing, cavity evacuation, and bow wave generation), mathematical catastrophe theory which explains formation of electron density singularities (cusps), and collective radiation due to nonlinear oscillations of a compact charge.