In MediaWiki 1.25 there was an API change announced:
list=deletedrevs becomes list=alldeletedrevisions prop=deletedrevs becomes prop=deletedrevisions
APISite.deletedrevs uses API deletedrevs. This should use list alldeletedrevisions or prop deletedrevisions on 1.25+ (See APISite.version). The version test could be more specific. i.e. if it was released in 1.25wmf7 (as announced, but may not be reality), that can be used as the version test.
pywikibot/data/api.py includes a TODO which can be removed when this is completed.
See also T74733: Implement site.undelete.