I see that some of the trees posted at ancestry.com indicate your research subject died 31 Jul 1914 - Oklahoma City, Oklahoma County, Oklahoma. Have you already tried procuring his death record and/or will/probate file from Oklahoma County? These records may indicate his parents' names.

It also may be worth contacting the Oklahoma City library system to request an obituary lookup.

Was the online marriage record you found a complete image, or just an index entry? If it was only index data, it may be worth ordering a copy of the original record to determine whether John's specific place of birth or parents' names were listed.

I note that there are quite a few McMILL*N entries in censuses for that general area.