There are a few options that may mean you don't have to code anything:
- A patch for the entityreference module to add this type of cleanup: https://www.drupal.org/node/1368386
- A module to handle cleanup: https://www.drupal.org/project/reference_delete
- A sandbox module to handle cleanup: https://www.drupal.org/sandbox/drothstein/1775816
I would go with one of those if possible instead of writing custom code.
Seeing as you do want to run custom code though I would suggest reading up on how those solutions work and implementing something similar, but with your own custom logic.
For example in the issue in that first link they discuss 3 different ways of doing the deletions and some of the pros and cons of certain possible solutions, so I think that information would be useful to you in implementing your own.
Although I don't know your exact requirements I would suggest that doing this at the validation stage is not a good idea because it means it is possible for you to delete referencing entities at validation stage and then something could stop the deletion of the referenced entities after your code runs and you will have deleted the reference when you shouldn't have.
It should be done later than the validation stage.
That patch issue suggests maybe hook_entity_delete(), which I think is a better place for it, however in that issue they also mention possible page timeouts if there are lots of references to delete.
The code in those 2 modules may also be useful to you but I haven't read those.
EDIT: just had a quick look an the reference_delete module also uses the entity delete hook.