Tulloch is a Scottish locational surname of Medieval origin, from the Gaelic word Tulach - literally a small hill. The name has been given to verious places in Scotland including a settlement near Dingwall in the north of Scotland and the nearby Tulloch Castle. 
In 1254, the Registrorum Abbacie de Aberbrothoc' (Register of Arbroath Abbey) recorded an estate called "Tulloch" or "Tulach", in Angus, northeast Scotland, which is the first record of the name. This village is now called "Tulloes" and is in the Parish of Dunnichen. 
There are currently ca. 6,000 Tullochs in the world - including 2,000 in Britain , 1,700 in the United States , 1,200 in Canada  and 600 in Australia.  and 4,300 people with the surname Tullis , which is believed to derive from Tulloch.
Earliest recorded Tullochs
The first recorded person with the surname was Walter de Tulach, who was listed as the "Keeper of Kildrummy Castle" in 1363. He receiving a charter of the lands of Kinnell, Forfarshire, in 1390 from Lord Hugh Fraser of Lovat, the Chief of Clan Fraser.  Later he received a charter of Bonnyton - a hamlet between Maryton and Carcary, just west of Montrose - from King Robert II.
Meanwhile, a Nicholas de Tolach, possibly unrelated, was recorded as a witness in a document dated 1364 from Brechin, Scotland, which is 8 miles west of Montrose. 
In 1399, King Robert III of Scotland granted John Tulloch, the office of "Keeper of the Moor of Monrommon", which is about 4 miles southwest of Brechin. This office was held by the Tullochs of Hillcarnie family until 1583 when it was sold to the Wood family. 
Their son, Thomas Tulloch was promoted in 1418 from the presbyter of Brechin to be the Bishop and Governor of Orkney. He was the first in a long line of Tulloch clergymen, many appointed by local lairds exercising their rights of patronage. Thomas appointed three relatives - Malise, David and then Thomas - as the Archdeacon of Shetland and Andrew de Tulloch as the Archdeacon of Orkney.
He resigned in 1461 in favour of his uncle, William de Tulloch. William was promoted to Bishop of Moray in 1477 and was Keeper of the Privy Seal of Scotland from 1470 to 1482. A different, possibly unrelated, Thomas de Tulloch became the Bishop of Ross in 1440 and a Hector Tulloch became the Archdeacon of Caithness in 1445. A Robert de Tulloch was Archdeacon of Moray in 1443 and a Thomas de Tulloch was Archdeacon of Lothian from 1441-1444.
The Tulloch Bishops were known in the history of Orkneys for settling Scottish people, including many of their relatives, on the Northern Islands, which had just been granted from Norway to Scotland as a wedding dowry. As a consequence, by 1881 there were 719 families on Orkney and Shetland, which was over a third of all Tullochs in Scotland and more than any other county.
Back in Angus, Bishop William's brother, John Tulloch, was created Baron of Craigneston in 1494. His great great grandson, Robert Tulloch, was created in 1574 the first Laird of Tannachy, a hamlet just outside Forres, in Moray, 100 miles northwest of Montrose. Robert's son, Patrick Tulloch, was Archdeacon of Moray from 1613 to 1638.
Another Tulloch family recorded on werelate are the descendents of Robert Tulloch, who was born in 1740 and lived in East Lothian, near Edinburgh. His descendents lived in East Lothian and Midlothian in 1881 (see below). In 1883, his descendent William emigrated with his family from to Queensland, Australia, where several Tulloch families now live.
In 1881, there were just under 2,000 people with the Surname in Britain, mostly living in Shetland, Orkney and the Highlands of Scotland.  The distribution of families in Scotland and England was :
By 1998, the number of Tullochs in Britain had reduced to 1,901, with Shetland still having the largest population but by now spread across Scotland with a family in Yorkshire. 
Between 1852 and 1891, 86 people emigrated from Britain to the United States. By 2010, the number of Tullochs in the United States had increased to 1,250. 
Six people who are male line descendants of a Tullis, who believe they are descended from Tullochs, have been tested for their Y DNS and found to match. . The full results for one of these people is here was shown using this calculator to be Haplogroup R1a. The closest Haplotype is "R1a #12", which is most frequently found among Romani, Viking and Kabardinian groups. Given the geographical context, this supports a link to the Viking settlement of Britain between 800-1000.