Hi
I am sorry I can't help with the marriage of John MILLS and Elizabeth HOOK which, if it took place in England would certainly give you the name of John's father.
Taking up the clue of William born 1831, I found a William aged 9 in the 1841 census, living with his family in Swinsidehall in Oxnam parish. head of household is Thomas, 50, an ag lab, and there is also Jane, 40, Sarah 14, Margaret, 12 and Thomas, 3.
In 1851 at Crookhouse, Linton parish, there is Thomas, 65, ag lab born in Eckford, Jane 55, born in Morebattle, and Thomas 13, also born in Morebattle.
The names of this couple fit well with the names of John and Elizabeth's children.
Have you found John Mills on the 1851 census? It's just that at Mainside in Hownam parish in the Cheviots in 1851 there is a John Mills aged 29, described as a shepherd, born Eckford. He is listed as being married, but there is no wife or children with him. The census was taken in 1851 around lambing time- perhaps he had returned to Roxburghshire knowing extra labour would be needed, to raise money for the planned emigration? The birthplace of this John also sits well with the couple Thomas and Jane. (All the above named parishes are very close or adjacent to each other, by the way.)
Regards,
Lesley