A product of Dundee United's scouting and coaching network in the west of Scotland, Glasgow-born McKinlay was signed from Hamilton Thistle in 1986. He played in the 1988 Scottish Cup Final side at the age of 19, after only twelve Scottish Football League appearances. He went on to play over two hundred matches for United, but missed out on the club's 1994 Scottish Cup win due to suspension.
Following Dundee United's relegation in 1995, McKinlay requested a transfer. He was sold to English Premier League champions Blackburn Rovers in October 1995 for a fee of £1.75 million. After leaving Blackburn in 2000, McKinlay had brief spells with Bradford City, Preston North End and Clydebank. In 2002 he joined Leicester City, where he scored once in the Premier League, against Coventry City. In 2004, Fulham manager Chris Coleman signed McKinlay, primarily to assist the reserve squad.
McKinlay represented Scotland at under-21 and B international level before making his full debut in 1993. He made fourteen appearances for Scotland while a Dundee United player, the last two as a First Division player. He is one of only three players from that division to play at full international level for Scotland since 1975. In total he played 29 times for Scotland between 1993 and 1998, scoring four goals. He was selected for the Euro 1996 and 1998 World Cup squads, making one appearance at each tournament.
On 21 December 2007, Fulham first-team coach Ray Lewington and reserve team manager McKinlay took over after manager Lawrie Sanchez was sacked. Roy Hodgson was appointed nine days later. McKinlay coached Fulham's reserve side and developed youth talent, and in 2012 became Northern Ireland assistant manager, but returned to Fulham to manage the side's 4–0 defeat at Everton, on 28 April 2012 due to Martin Jol's chest infection and was again in charge on Merseyside, for Fulham's win against Liverpool. On 2 December 2013, McKinlay left Fulham after Martin Jol's departure a day earlier.
McKinlay was appointed as Watford first-team coach, under head coach Óscar Garcia, on 26 September 2014. McKinlay replaced Garcia a few days later as head coach, after the Spaniard resigned due to suffering from ill health. McKinlay relinquished his role as Northern Ireland's assistant manager after becoming the Watford manager. After just eight days in the job, McKinlay was replaced as Watford head coach by Slaviša Jokanović. McKinlay had taken charge of two matches, a win against Brentford and a draw with Brighton.