Recently one of our users got the below error while trying to merge Lead record.
The user was having the Merge rights. However, the user was missing Share rights on the Lead entity. He already had create, write, delete, append and append to rights.
More details here
Giving Share rights fixed the issue.
Hope it helps..