When you debug the parent query you will get the id of the lookup only.
To get the vale of the child field you have to explicitly output it.
Region__r.Division__c
Another way is the getSObject method if you need the sObject
Region__c tmp = (Region__c)accs.getSObject('Region__r');
System.debug(tmp.Division__c);
Note you can only get field explicitly in the query you created the SObject from