Without a third party cleaning app? (I don’t recommend if you aren’t technically inclined BTW, most are shit) you need to go in to your system settings, find the app in question, and clear cache and local storage before uninstalling.

The login credentials are likely saved without your Google Account, not something the apps are leaving behind. You could test it by removing your Google account from your phone, signing in with a temp Google account. And then installing those apps again, and seeing if the login credentials are still there.

It is likely that the apps you uninstalled actually support automatic backup. When you uninstall an app that supports automatic backup, their data backed up into your Google account will be restored next time you reinstall them.

I think you can review those backups from the Google Drive app. Open Google Drive app, go to settings, then find “auto backup for apps / backup and reset”. Mine says I have 79 apps backup with 99MB backup data in total. Not sure how to actually delete individual backup though. Some says if you delete the app from your play store download history, it’ll clear the backup data, but can’t verify it right now.

In summary, the data is deleted from your phone when you uninstall the app, but if the app support automatic backup, it’ll download the last backup data from your Google Drive account when you reinstall the app.

I think what’s happening is the app is using Android’s account manager to store credentials. These are part of the system and not removed when an app is uninstalled.

If this is what’s happening then you can go to “Passwords & accounts” in settings and find the account to remove. There really shouldn’t be any data left over and you shouldn’t need to clear app data and cache before uninstalling, the system takes good care of that when the app is uninstalled.