SharePoint 2013 - User Profile Cleanup Timer Job

Diagrams below explain how the user profiles are getting imported by User Profile Application in SharePoint 2013 and then how they are deleted from the SharePoint.

MySites is created when user accesses the MySite Host Site.

After the profiles are marked deleted in the UserProfile_Full table, Cleanup job takes care of the dirty work.

Ref: http://blogs.msdn.com/b/kaevans/archive/2012/06/25/top-recommendations-for-managing-the-my-site-cleanup-timer-job.aspx