Robust oscillations have recently been observed in a synthetic gene network composed of coupled positive and negative feedback loops. Here we use deterministic and stochastic modeling to investigate how a small time delay in such regulatory networks can lead to strongly nonlinear oscillations that can be characterized by "degrade-and-fire" dynamics. We show that the period of the oscillations can be significantly greater than the delay time, provided the circuit components possess strong activation and tight repression. The variability of the period is strongly influenced by fluctuations near the oscillatory minima, when the number of regulatory molecules is small.