The authors examine the frequency distribution of second-order recurrence sequences that are not p-regular, for an odd prime p, and apply their results to compute bounds for the frequencies of p-singular elements of p-regular second-order recurrences modulo powers of the prime p. The authors’ results have application to the p-stability of second-order recurrence sequences.