"Wallace as a name came over with William the conquerer so his language would also have been French or Flemish." The ordinary people at the bottom of the pile would have spoken different dialects of English, some would have spoken Gaelic(from the Highlands) and it is also possible that Welsh or the northern version of it still survived in different parts of Scotland and Northern England - there is evidence for this in place names, e g Aberdeen - mouth of the river Dee, and folklore,"

I don't think that it is at all certain that the name Wallace came over with the Normans. In his "Surnames of Scotland" Professor Black gives the various theories but comes to the conclusion that "Wallace is most probably simply a native name meaning Strathclyde Briton" and of course as Wallace lived in what had been Strathclyde it is very possible. Gaelic at that time was spoken throughout much of Scotland and not just in the Highlands. The division into Gaelic speaking Highlander and Scots speaking Lowlander is a later phenomena. It is true that Aberdeen comes from a P-Celtic language. It is bang in the middle of the P-Celtic Pictish speaking area. The P-Celtic Pictish language is thought to have been closely related to the Britonnic/Cumbric/Welsh which was spoken in the south of Scotland.