During 1997, the BL Lac object Mkn 501 went into an extraordinary state of high X-ray and TeV gamma-ray activity, lasting more than 6 months. In this paper we report on the TeV emission characteristics of the source in the subsequent years of 1998 and 1999 as measured with the Stereoscopic Cherenkov Telescope System of HEGRA (La Palma, Canary Islands). Our observations reveal a 1998-1999 mean emission level at 1 TeV of 1/3 of the flux of the Crab Nebula, a factor of 10 lower than during the year of 1997. A dataset of 122 observations hours with the HEGRA telescope system makes it possible to assess for the first time the Mkn 501 TeV energy spectrum for a mean flux level substantially below that of the Crab Nebula with reasonable statistical accuracy. Excluding the data of a strong flare, we find evidence that the 1998--1999 low-flux spectrum is substantially softer (by 0.44+-0.1(stat) in spectral index) than the 1997 time averaged spectrum. The 500 GeV to 10 TeV energy spectrum can well be described by a power law model with exponential cutoff: dN/dE ~ E^(-alpha) exp(-E/E0) with alpha=2.31+-0.22(stat), and E0=5.1 (-2.3+7.8)(stat) TeV. Within statistical accuracy, also a pure power law model gives an acceptable fit to the data: dN/dE ~ E^(-Gamma) with Gamma=2.76+-0.08(stat). After presenting the 1998-1999 TeV characteristics of the source we discuss the implications of the results.