Carol,
Well, I guess there are quite a few avenues to follow up.
1. As you say, if you can find a marriage of Agnes to John WALLACE, that could help - but it might not be possible to find a record.
2. I suggested that you yourself look at the film of the Eckford Roxburghshire Scotland parish register (or purchase a copy of the entry from GROS) for the baptism of William WALLACE, bap 23 Jun 1846, parents John WALLACE and Agnes NILSON. It's possible that NILSON is a transcription error and you might see the name as HILSON; alternatively, of course, it might definitely be NILSON.
3. From your further information, it seems that there are also two older sons, both born in England (where Statutory Registration started in Sep 1837 compared with a start date of 1855 for Scotland) - John WALLACE (10 mths in 1841; 10 in 1851) and James WALLACE (7 in 1851) both born Northumberland. As both were born in England, it should be possible to get their birth certificates - Agnes's maiden surname might be crystal clear on these.
The IGI has the following entry:
WALLACE John, bap 2 Aug 1840, Lucker Northumberland England, parents John WALLACE and Agnes
FreeBMD has the following entry:
WALLACE John, Tynemouth, Mar qtr 1840, Vol 25 Page 379
However, Tynemouth and Lucker, from the map, are a long way apart ...
FreeBMD has a couple of possibilities for a James WALLACE b Northumberland ca 1844 +/- 2.
But it would mean buying the certificates ...
JAP
PS: For information - you mentioned that they were in "Heaton or Heiton" in 1851. Gazetteers list, and maps show, a place called Heiton in Roxburghshire - about half-way between Kelso and Eckford.