I think the answer is "no", but I thought I would check with the experts out there.

If an employee is terminated effective immediately, but his employer pays the employee for a month after his termination (ie: severance), does the month after the termination count towards the employee's service?

I too think "no". There are no hours of SERVICE. The pay is not for work or availability for work. It's a severance type pay.

I'd agree too but add the caution to double check your plan text (definitions of service, employment, hours of service, earnings, etc). Just be sure it's truly severance and not paid leave of absence. The termination date you record in your HR/payroll system will be important.

Masteff's comment about checking plan language is, of course, good. Masteff's comment about termination date recorded in your HR/payroll system also has implications for any group health coverage you may provide employees, and COBRA continuation notices etc.

Several prior discussion threads on this topic. You may wish to try the Search feature.
A keyword such as "severance" may help.