This is by no means a complete list; I'm sure there are others out there.

Mac = son of

Nairn — Probably from Airn and Cairn, meaning "land of the new Irish"; when the Gaels landed in Kilmartin, Argyll, they would build a cairn and claim the place as their own. Possibly associated with Clan MacKenzie.
Napier — from "Lennox had na peer" meaning "no equal"; from a statement by Alexander III. Records show this family in Scotland as early as 1140.
Neil — associated with Clan MacNeil. Neal, Neill, Neilson.
Nelson — associated with Clans Gunn and MacNeil.
Neish — associated with Clan MacGregor.
Nicholson — MacNeacail, Clann 'IcNeacail (Nicolsons). From the Lowlands of Scotland around Dumfries, but also found on the Isles of Skye and Lewis as MacNichol, who trace their ancestry to an ancient family of Vikings. Nicolson, MacNichol.
Nisbet — from the barony of Nesbit in Berwickshire; first recorded was Philip Nesbit, a sheriff in 1493. Some of the family left for Sweden in the 16th C. Nisbett, Nesbett.
Nish — associated with Clan MacGregor.
Niven — associated with Clan Cumming and MacKintosh.
Nixon — associated with Clan Armstrong.
Noble — associated with Clan MacKintosh.
Norie — associated with Clan MacDonald.
Norman — associated with Clan Sutherland.

O'Drain — associated with Clan MacDonald.
Oliver — associated with Clan Fraser.
O'May — associated with Clan Sutherland.
O'Shaig — associated with Clan MacDonald.
O'Shannachan — associated with Clan MacDonald.
O'Shannaig — associated with Clan MacDonald.
Ogilvie — Mac Ghille Bhuidhe. Ancestry traced to Gillibride, second son of Ghillichriost, earl of Angus. He was given the barony of Ogilvy c. 1163. Branches include Inverquharity and East Lothian. Ogilvy.
Oliphant — of Norman origin. David Holifard saved his godfather, David I, at the Rout of Winchester in 1141. William Oliphant held Stirling Castle against Edward I of England's seige.

Park — associated with Clan MacDonald.
Parlane — associated with Clan MacFarlane.
Paton — associated with Clans MacDonald and MacLean.
Patrick — associated with Clan Lamont.
Paul — associated with Clan Cameron and MacKintosh.
Pearson — associated with Clan MacPherson.
Peebles — associated with/sept of Clan Hay
Peterkin — associated with Clan MacGregor.
Petrie — associated with Clan MacGregor.
Philipson — associated with Clan MacDonald.
Pinkerton — associated with Clan Campbell.
Piper — associated with Clan Murray.
Pitullich — associated with Clan MacDonald.
Pollard — associated with Clan MacKay.
Polson — associated with Clan MacKay.
Porter — associated with Clan MacNaughton.
Pratt — associated with Clan Grant.
Preston — related to the de Preston family of Ireland; documents show an Alured de Preston in Scotland in the 13th C.
Pringle — taken from the name of lands in Roxburghshire; the family is first recorded during Alexander III's reign. They were also one of the Riding Clans of the Scottish Borders.
Purcell — associated with Clan MacDonald.

Quirie — associated with House of Gordon; integrated into Clan Gordon during the years following the invasion of Scotland from Normandy, France.

Raith — associated with Clan MacRae.
Ramsay — Ramsaidh. First recorded in Scotland was Simon de Ramsay, an Anglo-Norman who received lands from David I; after the Battle of Marston Moor and Philiphaugh, William Ramsay was made the first earl of Dalhousie in 1633.
Randolf — associated with Clan Bruce.
Rattray — ancestry traced to Adam de Rattreiff in the 13th C. They followed the Murrays of Atholl, but were not a branch.
Reidfurd — associated with Clan Innes.
Reoch — associated with Clans Farquharson and MacDonald.
Revie — associated with Clan MacDonald.
Riach — associated with Clans Farquharson and MacDonald.
Richardson — associated with Clans Buchanan and Ogilvie.
Risk — associated with Clan Buchanan.
Ritchie — associated with Clan MacKintosh.
Robb — associated with Clan MacFarlane.
Roberts — associated with Clan Robertson.
Robertson — Robasdan, MacDhonnchaidh, Mac Raibeirt, Clann 'IcDhonnchaidh, Clann Donnchaidh, Na Robasdanaich (Robertsons). The ancestor was Duncan or Donnachaidh Reamhair, who led the clan for Robert Bruce at Bannockburn and was himself descended from Celtic earls of Atholl. The name came from a later chief, Robert, during the reign of James I. They also fought with the Stuarts in the Jacobite risings of 1715 and 1745. Donnachaidh, Dobinson, Macrobbie, MacRobert, MacRobie, Roberst, Robson, Roberts.
Robinson — associated with Clans Gunn and Robertson.
Robison — associated with Clans Gunn and Robertson.
Robson — associated with Clans Gunn and Robertson.
Rollo — lands of Duncrub were received by a John Rollo in 1380. Robert, the 4th baron, supported James Francis Stuart (Old Pretender) in 1715, but was forced to surrender.
Rome — associated with Clan Johnstone.
Ronald — associated with Clans Gunn and MacDonald.
Ronaldson — associated with Clans Gunn and MacDonald.
Rorison — associated with Clan MacDonald.
Rose — Rςs, Rois, Na Rςsaich (Rose(s)). Traced back to the Roses of Kilravock in Nairn during the reign of King David I. Hugh Rose built Kilravock Castle in 1460; Bonnie Prince Charlie stayed at the castle before the 1746 Battle of Culloden.
Ross — Ros, Na Rosaich (Ross(es)). Claims Norman descent and possibly descended from Gilleon na h-airde. One of his descendants was Fearcher MacinTagart, who helped put down a rebellion for the Crown in 1215. The Ross family who held lands in Ayrshire and Renfrewshire in the 12th C. may be descended from Godfrey de Ros from Yorkshire. Vass, Wass.
Roy — associated with Clan Robertson.
Rusk — associated with Clan Buchanan.
Ruskin — associated with Clan Buchanan.
Russell- connected to the French name Rosel. The Russells of Aden in Aberdeenshire trace ancestry to an English baron who came with Edward III of England and stayed in Scotland after the siege of Berwick. Allied with with Clan Cumming.
Rutherford — a once rich and powerful Border family who took their name from the lands of Rutherford in Roxburghshire. The name appears in documents of William the Lion and Alexander II. Daniel Rutherford (b. 1749, Edinburgh) discovered nitrogen.
Ruthven — ancestry traced to Swan, son of Thor, son of Swein, who held lands in Perthshire and Clydesdale; Thor took the name de Ruthven. Patrick Ruthven was one of the Scottish lords involved in the murder of Mary, Queen of Scots' secretary, David Rizzio. His son, the first earl of Gowrie, kidnapped the young king and held him for ten months in what is known as the Ruthven Raid. The king escaped and Gowrie was executed in 1584. Because of the later Gowrie Conspiracy, the name was proscribed for forty years until its reinstatement in 1641.

Sanderson — associated with Clan MacDonald.
Sandison — associated with Clan Gunn.
Saunders — associated with Clan MacAlister.
Schaw — a Lowland surname recorded in the 13th C.; the northern branch of the clan descended from Shaw, son of Gilchrist, grandson of the 6th chief of Clan Mackintosh. The other branch is descended from Adam, second son of Rothiemurchus. Shaw.
Scobie — associated with Clan MacKay.
Scott — Scotach, Scot. A Border clan whose ancestry traces to Uchtredus filisus Scoti of the 12th C. His two sons, Richard and Michael, were the heads of two branches of the family; linked by marriage to the duke of Monmouth and the powerful Douglas dukes of Queensberry. Sir Walter Scot, the writer, was connected with Hugh Scott of Polwarth. The Scotts were a powerful Border clan in the 16th C., with the ability to raise 600 warriors to battle.
Scrimgeour — first mentioned in 13th C. Fife documents. Two documents of 1298 grant Schyrmeschur, son of Colin, son of Carun, the honor of carrying the king's banner in war, and made him a constable of the Castle of Dundee.
Semphill — from Renfrewshire and ancestry is traced to Robert de Semple, c. 1280. They were hereditary sheriffs of Renfrew.
Seton — the family played an important role in Scottish affairs and built splendid houses, including Seton Castle where Mary, Queen of Scots, lived after Rizzio's murder.
Shannon — associated with Clan MacDonald.
Sharp — associated with Clan Stewart.
Shaw — Mac Ghille-Sheathanaich. Associated with Clan Chattan.
Sherry — associated with Clan MacKinnon.
Sim — associated with Clan Fraser of Lovat.
Sime — associated with Clan Fraser of Lovat.
Simon — associated with Clan Fraser of Lovat.
Simpson — associated with Clan Fraser of Lovat. Simson.
Sinclair — Mac na Ceardadh. The clan's founder was William Saint Clair, son of Robert De Saint Clare of Normandy. Records show a Henry de Sancto Claro supported Robert Bruce and signed a letter to the pope in 1320. It is said that William St. Clair built Roslin Castle; the Highland Castle of Mey was a Sinclair stronghold built in 1568. Sinclare, St. Clair, Sinclaire, St. Claire, Sinkler.
Skene — the ancestor of the clan received the barony of Skene from Malcolm Canmore. The Skenes of Skene died out in the 19th C. Skeen.
Skinner — associated with Clan MacGregor.
Small — associated with Clan Murray.
Smart — associated with Clan MacKenzie.
Smith — Mc a' Ghobhainn, Clann a' Ghobhainn (Smiths). Associated with Clans MacKintosh and MacPherson.
Snodgrass — of local origin, deriving from the name of the dwelling place or locality where a bearer once lived. In one instance, the name can be traced to the lands named Snodgrasse in Ayrshire, and the name literally meant, "a dweller at the smooth, grassy land". In medieval Scotland it was common practice to identify a man with the area from which he hailed and to refer to him in this manner. Thus a resident of Snodgrasse usually adopted the name of their native soil as their family name. There was also a certain civic pride involved in registering one's native town as one's family name. Early instances of the name were generally prefixed with "de" meaning "of", a preposition used to denote surnames of local origin. The earliest instance of the name occurs in the Scottish Rolls and the listings are entered in Scots Gaelic one Adam Snorgyrs is listed as being the bailie (bailiff) of Are (Ayr) in 1372. The modern form of the name began to appear during the 16th C. one Patrick Snodgrass was admitted Burgess and Freeman of Glasgow in 1578. In Glasgow the surname frequently appears as Snodgers where a notable family of this name resided during the Middle Ages they were recorded in the Glasgow Protocol Books as being significant maltmen and brewers. One Margaret Snodgers inherited this firm from her brother John in 1621. *extensive info provided by JCSnodgrass.
Somerville — derived from a town in Normandy. David I gave lands in Lanarkshire to William de Somerville when he came to Scotland with him. Folklore says another William de Somerville got the lands for killing a monster that was terrorizing the area.
Sorely — associated with Clans Cameron and MacDonald. Sorley.
Spalding — from the town of Spalding in Lincolnshire. First recorded in 13th C. documents. Peter de Spalding, a burgess, helped the attackers of Berwick in 1318. Robert Bruce game him lands in Angus.
Spence — associated with Clan MacDuff.
Spens — said they are descended from Duncan, 4th earl of Fife. Patrick de Spens had lands in Berwickshire in the 15th C; and John de Spensa of Perth held land in Menteith.
Spittal — associated with Clan Buchanan. Spittel.
Sporran — associated with Clan MacDonald.
Stalker — associated with Clan MacFarlane.
Stark — associated with Clan Robertson.
Stenhouse — associated with Clan Bruce.
Stewart — Stiωbhart, Na Stiωbhartaich (Stewarts). The Royal House of Steward has a family tradition that they are descended from Banquo, thane of Lochaber; but the family has been traced to Alan, Seneschal of Dol, a Celtic noble and are basically a Lowland family. Alan's third son, Walter Fitz Alan was High Steward of Scotland under David I. Walter's grandson, Walter, adopted the title Steward as a surname. Bruce's grandson, Robert Stewart, was the first of the Royal House of Stewart. Prince Charles Edward Stuart (Bonnie Prince Charlie), son of James Francis (the Old Pretender), is the best known of the family. His uprising was ended at Culloden Moor in 1746, and he died in Rome in 1788. Stewart was changed to Stuart after Mary Stuart, Queen of Scots. Stuart, Steuard, Steuart.
Stirling — first appears as a surname in the 12th C. John Stirlin of Moary swore fealty in 1291, and the Stirlings of Keir were established there in the 12th C. Stirlin.
Storie — associated with Clan Ogilvie.
Stringer — associated with Clan MacGregor.
Sturgeon — connected with the Dumfries area as early as the 1500s, with Andrew and John Sturgioun noted in records as witnesses in Dumfries in 1544. Allied with Clan Maxwell.
Summers — associated with Clan Lindsay.
Sutherland — Sutherlarach. Derived from the placename Sutherland, which the Norsemen of Caithness and Orkney called Southland. Ancestry is traced to the Celts who retreated before the Norse invaders. Hugh Freskin received the lands of Sutherland from King William the Lion in 1197. The first duke of Sutherland, George Granville Gower, built the town of Golspie. His is blamed for excessive Clearance evictions that drove most of his tenants overseas.
Suttie — associated with Clan Grant.
Swan — associated with Clan Gunn.
Swanson — associated with Clan Gunn.
Swinton — possibly of Anglian origin. Hugh of Swinton and his son Duncan received the thanedom of Arbuthnot from Walter Olifard. In the 15th C., some of this family went to France, where the name changed to Vincton.
Syme — associated with Clan Fraser.
Symon — associated with Clan Fraser.

Taggart — associated with Clan Ross.
Tarrill — associated with Clan MacKintosh.
Tawesson — associated with Clan Campbell.
Tawse — associated with Clan Farquharson.
Thain — associated with Clans Innes and MacIntosh.
Thomson — MacThςmais, Clann 'IcThςmais (Thomsons). Thompson.
Todd — associated with Clan Gordon.
Tolmie — associated with Clan MacLeod.
Tonnochy — associated with Clan Robertson.
Torry — associated with Clan Campbell.
Tosh — associated with Clan MacKintosh.
Toward — associated with Clan Lamont. Towart.
Train — associated with Clan Ross.
Trotter — "messanger". Trotter of Prentannan was head of the Border clan with this name in Berwickshire. Those associated with Morton Hall in Midlothian date their origin back to the reign of Robert II.
Turnbull — tradition says the name comes from William of Rule, who saved Robert Bruce from a wounded bull. Because of this incident, he became known as Turn-e-bull.
Turner — associated with Clan Lamont.
Tweedie — said that this old clan originated from a water spirit of the River Tweed. They held their lands of Drumelzier for 300 years until the land was taken away by Charles I.
Tyre — associated with Clan MacIntyre.

Ure — associated with Clan Campbell.
Urquhart — Urchurdan. From the lands of Urquhart on Loch Ness. William Urquhart, a sheriff of Cromarty, married a daughter of the earl of Ross in the 14th C. The family seat at Craigston Castle has been held since 1604.

Vass — associated with Clans Munro and Ross.

Wallace — Uallas. "Strathclyde Briton", a native Gaelic name. It's well known in Ayrshire and Renfrewshire in the 13th C. First records of the surname mentions a Richard Wallace (or Wallensis) in the 12th C. Malcolm Wallace was patriot William Wallace's (1274-1305) father. William led the revolt against the English and was brutally executed in London. It is said that he took up arms after his wife was murdered by the English. Wallis.
Walters — associated with Clan Forbes.
Wardlaw — probably of Anglo-Saxon origin, although their name was taken from Wardlaw nearly Beauly. Henry Wardlaw of the 15th C. was bishop of St. Andrews and founded the University of St. Andrews.
Wass — associated with Clans Munro and Ross.
Watt — associated with Clan Buchanan.
Weaver — associated with Clan MacFarlane.
Webster — associated with Clan MacFarlane.
Weir — from a Norman name from Vere, France; the first Scottish record of the name mentions a Radulphus de Ver, who was captured at Alnwick with William the Lion. His descendants, the Weirs of Blackwood, only appear in records in 1400. Some of the Macnairs of Cowal anglicized their name to Weir.
Wemyss — from a placename, the lands of Wemyss in Fife. First recorded of this name was Michael de Methkil, aka Michael de Wemy.
Whannell — associated with Clan MacDonald.
Wharrie — associated with Clan MacQuarrie.
Wheelan — associated with Clan MacDonald.
White — associated with Clans MacGregor and Lamont.
Whyte — associated with Clans MacGregor and Lamont.
Wilkie — associated with Clan MacDonald.
Wilkinson — associated with Clan MacDonald.
Will — associated with Clan Gunn.
Williamson — associated with Clans Gunn and MacKay.
Wilson — associated with Clans Gunn and Innes.
Winchester — sept of Clan Cunningham.
Wood — a placename, "one living near a wood"; very widespread in Scotland, the most important branches of the family settled in Morayshire and in the Borders near Lanarkshire.
Wright — associated with Clan MacIntyre.
Wylie — associated with Clans Gunn and MacFarlane.

Yule — associated with Clan Buchanan. Yuille, Yuille.