What branch of the military? If it's not the Army, you could try to get records if he is a direct ancestor.
The 1940 census may help when indexing is complete.
Do you have any theories about the reason for the name change? During that time period very little was required to effectively change your name.
Did you try Social Security records? That's the one thing that was usually accurate. Have you been able to obtain a Social Security Number for Miller/Schlenker? Due to new Privacy Laws, I don't know how much help you will receive now from the SSA.
Years ago, while ordering a headstone for an ancestor, we found a discrepancy in his name. Social Security was able to provide the correct information. They also said that Military info may be incorrect regarding age. Many men lied about their age to enter the service, you have to take that with a grain of salt.
As far as legal name changes, you would need to know which state and possibly the county to find a record. Each state is different. Some states allow aliases without any paperwork as long as the alias is not used for illegal purposes.
Good Luck!
Rel@ively,
Patrice