There is no such thing in SharePoint as "versioning for the delete process". When an item is deleted, the item and it's entire version history move to the recycle bin, and eventually disappear into oblivion.
You cannot hook an approval process to the delete process, and there wouldn't be any history to that either. If you trigger your Flow on item deleted, the item is already in the recycle bin by the time your actions run.
What you will want to do is implement your own "soft delete" process. This is a process often used in databases where a table is given a Boolean flag named something like
isDeleted, and then all views and queries only return data where that flag is
false, and when a user "deletes" an item, the code just marks that flag "true", so the data never gets deleted, but behaves as if it has.
First, create a custom permission level for users to retain contribute rights without delete privileges for this list.
Then create two yes/no columns,
IsDeleted. We're creating two separate columns because in SharePoint, it's the only way to track if a specific field just changed. Make sure to make the
IsDeleted column hidden.
Then instead of a separate Flow, add a conditional branch to your On Item Modified Flow, checking when
NeedsDeleted 'equals' true and
NeedsDeleted 'does not equal' IsDeleted, which means this branch will only be executed when a user checked the
NeedsDeleted box. Inside that Flow condition branch, do your approval process, and if approved, then set
Depending on how strictly you want to hide those "deleted" items, you can either make sure all your list views filter out items with this column set to
true, or in your Flow you can set item level permissions on the item to remove Read permissions from everyone except Admins.