Reference: Records from issues of the 'Railroad Gazette' dated October 1890 and March 1891 indicate this:
click here
click here
The former, mentions the introduction of a new fast mail service between Calcutta and Kalka through the Delhi-Umballa-Kalka (DUK) railway, to be introduced 'soon'. This account dates from October 1890, a few months before the DUK line was opened.
The...
more...

latter, dated March 1891 mentions about a delay in the opening of the DUK line due to concerns about the quality of the permanent way. The line was opened on March 1st, 1891. And presumably, the Calcutta-Kalka mail was introduced either on this day, or shortly afterwards.
By 1895, the E.I.R's Calcutta-Kalka mail was operational and was also the fastest train in the sub-continent - click here
While it is popularly known that the Kalka mail is the extended form of the Calcutta-Delhi mail train introduced in 1866, there isn't much evidence in this regard. Firstly, end-to-end direct train service between Calcutta and the East bank of the Jamuna at Delhi (Delhi Shahdara) commenced from 15th August, 1865 after the bridge over the Jamuna at Allahabad was opened. The bridge across the Jamuna at Delhi was opened in January, 1867 after which trains started pulling into Delhi. As such, the often quoted date of January 1st, 1866 doesn't hold any particular significance as far as end-to-end connectivity between Calcutta and Delhi is concerned. The initial train was also a generic mail train and was not a named service (like the more famous Frontier mail or Deccan Queen).
Very likely, the direct successor to the original Calcutta-Delhi mail train (commencing in 1865) is the present day 13005/06 Howrah-Amritsar express, known in pre-partition days as the Punjab mail. As early as 1884, there are records of a 'Punjab mail' between Calcutta and Lahore which, by 1889, was running as far as Peshawar. Before the completion of the Bombay-Delhi link, through connection from Bombay to Lahore was provided through this Punjab mail, with the carriages switching at Allahabad. All timetables available after 1920 also show a through mail train between Calcutta and Lahore (Peshawar in pre-WW2 timetables - Refer to IRFCA gallery in the timetables section for the NWR 1930 TT). The timetable for the 'Calcutta mail train' running between Calcutta and Peshawar in 1889, is available here: click here
The Kalka mail started as a new dedicated service, the fastest in the sub-continent at the time of it's introduction, running at an average speed of ~48kmph end-to-end.