SOQL with ALL ROWS can be used in Apex to find number of Deleted Salesforce Pending Service Routing Records.

System.debug(
    'No of deleted PSRs is ' +
    [
        SELECT COUNT()
        FROM PendingServiceRouting
        WHERE IsDeleted = true
        ALL ROWS
    ]
);