Yep — if you increase the memory on the Options page, that will usually help for the new error you got. If the hosting provider has a lower limit, you may need to ask them to increase it on their end. (What they would need to change is the “memory_limit” option in the file “php.ini”.)
If you can’t get them to increase it, you may be able to disable some options like “Scan image files as if they were executable” (usually only needed for cleaning tough hacks), or removing large backup files from the server, if you have a backup plugin that stores large files on the server. You could also exclude backup files from scans using the field “Exclude files from scan that match these wildcard patterns”, if removing them isn’t practical.
Depending on where it is getting stuck, removing spam comments may help. In some cases, Wordfence is using little memory, but most of the limit is taken up by another plugin. I haven’t seen many of these lately, but sometimes disabling another plugin will help (especially if you have extra plugins enabled you don’t really need anymore.)
-Matt R