Generic Extension Method To Count Descendants
Peter already pointed out the main problem with your code: you're doing linear searches when looking for child-nodes, which will blow up to \$O(n^2)\$ for worst-case inputs (very deep trees). Indeed, a lookup table that maps a parent ID to child IDs is much more efficient, and ensures that your method remains \$O(n)\$ for all sorts of input.

Another problem is that your method does not guard against cyclic inputs - it'll run indefinitely. You may want to throw an exception instead, or otherwise prevent the start item from being added to the stack again. It's also a good idea to document this behavior.

Other notes:


There's no need to perform input validation in a separate method here: Count does not use yield, so the input validation will be performed immediately. Note that a modern alternative is to move the yielding part to a local function instead of to a separate method.
When throwing argument-related exceptions, it's better to use nameof(parameterName) instead of "parameterName". This lets the compiler protect you against typos, and works well with code refactoring tools.
I would rename T to TKey, selfReference to keySelector and parentReference to parentKeySelector. I think that better describes their purpose, and it's consistent with other Linq methods.
Use var to cut down on type name repetition: var variableName = new LongTypeName(...); is equivalent to LongTypeName variableName = new LongTypeName(...);.
As Peter already mentioned, there's no need for that keys set: you're only adding items with a known parent ID to the stack, so there's no point in verifying whether their parent ID is known.