Identified the issue.
I was eager loading the children using an include line when the entity was first loaded.
I did not eager load the children when I modified the object or when I retrieved it from the database again. As a result, the changes and additions were becoming unclear. Upon included the include during the upload, scenario #2 above was successful (the explicit clear was not needed)
db.Roles.Include("Children").FirstOrDefault(z => z.RoleId == RoleId);
Also related, make sure all the entities in the graph are coming from the same DB context if you see this issue when working with relationships across several tables!
Before getting data from the database, try disabling auto detect changes via
context.Configuration.AutoDetectChangesEnabled = false;
Then, on the particular role object you are modifying, set the state to modified.
context.Entry(role).State = EntityState.Modified;
I haven't personally done this on a self-referencing many-to-many table, but adding and updating entities in this way can prevent EF from inferring the wrong thing about what you are adding or editing.