What is the history of the check mark / tick mark?

From the OED (1928)

Tick sb.³

...

3. A small dot or dash (often formed by two small strokes at an acute angle), made with a pen or pencil, to draw attention to something or to mark a name, figure, etc. as having been noted or checked.

1844 Frazer's Mag. XXX 88/1
Neat pencil ticks indicated favourite passages.

Also

Tick v.¹

...

3. trans. To mark (a name, an item in a list, etc.) with a tick; to mark off with a tick as noted, passed, or done with.

1861 Dickens Great Expectations xxxiv
I compared each with the bill and ticked it off.

The etymology of both usages is apparently (but not definitely) from the Dutch tik, pat, light touch or tick, and tikken, to pat or touch lightly.

I posit that the first small down stroke is just a stylized attempt to avoid the small blot which, as anyone who has used a fountain pen knows, frequently appears as pen touches paper.

Further, the linguistic relation to tick in other usages as the smallest distinct form, whether as an insect or the movement of a clock, in this case would be "the smallest distinct mark with which to unobtrusively mark up a written document with pen or pencil."

Linguistically a check mark is simply any mark with which one has checked items. Various possible check marks include "x-es" and "tick marks", as well as a host of other small marks used by proof readers, editors, accountants (auditing firms require a multi-page glossary of all the various check marks used for their audit trails!), etc.

The origin story laid out in the wikipedia page seems to be a reinterpretation of an older symbol and its meaning at best, and pure invention at worse.

Critical Notes on Graeco-Roman Ostraca, Herbert C. Youtie (1945) makes a passing mention, in footnote 96, of the use of checkmarks in what seems to be 3rd or 4th century papyri written in Greek:

Horizontal lines are drawn also under Col. 1.10 and Col. 2.1, 8, 13, where no headings are used. They extend the full width of the column, as if to mark offsections of the text. In this they differ from horizontal check marks, which rarely run more than a few centimeters into the column (P. Mich. 4, plates 1–4). An oblique check mark precedes Col. 1.6. On the use of the oblique line in this way see P. Col. 2, p. 39.

If I am not mistaking he's referring to papyri from this collection (which seems to have several tomes, and of which Youtie is a co-author). You can see the plates at the end of the book.

The same author discusses the meaning in Parerga Ostracologica (1942), pp. 66–67:

In the left margin, toward the edge of the ostracon, the photograph reveals a large and bold cross, much like x, seemingly made by a second hand. This is the marginal decussis, which has become familiar as a check-mark from P. Col. II.1 Recto 6 (cf. p. 165); P. bibl.univ. Giss. vi.49 Verso. I. 8; P. Tebt. i.103, where it is followed by a heavy dot, which is also known as an accounting device (P. Tebt. iii.845, introd.); P. Tebt. iii.834, introd. In the tax rolls from Karanis (e.g., P. Mich. iv.224.507, 818, 824) it is used to mark [greek word]. In literary manuscripts it may mark an omission repaired in the margin or a passage for which a marginal scholion has been provided. In the Thucydides text in P. Oxy. xiii.1620, the decussis as well as other signs refer to variant readings entered in the upper margin.

Which, to me, reads like it means "checked/done/verified".

The symbol itself seems to predate this. In Ancient Egyptian Mathematics, Clara Silvia Roero (1994) (p 53–54 in this pdf preview) notes the use of check marks by ancient Egyptian scribes when doing multiplications and divisions (sorry for the poor formatting, the pdf preview is missing crucial formatting and possibly symbols):

To multiply 12 by 7, the scribe proceeded thus: 1 7 2 14 \4 28 \8 56 Totals 12 84 The first column contains the powers of 2 and the second one a factor of multiplication successively doubled. The scribe placed a check mark along side the numbers in the first column that totalled 12, i.e. 4 + 8; the sum of the corresponding numbers in the second column, i.e. 28 + 56, then produced the result. This algorithm for multiplication was based on the arithmetical property that any integer can be expressed uniquely as the sum of certain terms of the geometrical progression 2 °, 2 1 , 2 2 , ••• , 2 k, . . . . The technique for division was the same as that for multiplication. For these operations the ancient Egyptians sometimes used not only 2 but other multipliers too, such as 10. For example, in the Rhind Papyrus (problem 36 69) 1120 + 80 is calculated, a division with an exact quotient: 80 10 800/ 2 160 4 320/ Totals 14 1120 The scribe set out to obtain the dividend 1120 in the second column, so he multiplied the divisor 80 by 10 and then successively doubled it until a number was reached which, when added to 800, gave 1120. In this case the check mark was placed alongside the numbers in the second column that totalled 1120; the required quotient was then the sum of the corresponding numbers in the first column. This technique is simple enough when the two integers are divisible; when the quotient was not a whole number the scribe used fractions. This example is taken from the Rhind Papyrus (problem 24)

That too, to me at least, kind of reads like it means "checked/done/verified".

The Rhind Mathematical Papyrus dates to around 1550 BC, which makes the unsourced origin story suggested in Wikipedia seem dubious.

Discussing the other end of the fertile crescent, Life at the bottom of Babylonian society: Servile laborers at Nippur in the 14TH and 13TH centuries B.C. (2009), by Jonathan Stuart Tenney, discusses the use of checkmarks in Babylonia around the same period. I failed to access an online pdf version. Google Scholar offers this helpful preview snippet that leaves no doubt that, there too, it meant "checked/done/verified":

All allocations are intended as rations (AE.BA); and, if an allocation was disbursed, a check mark was placed to the left of the recipient's name.

(However, Ilmari Karonen in the comments raises that they were literally just marks, so while I leave this example so his comments are in context, disregard it.)

Put together, I've no idea of the symbol's origin, but it seems to me that the symbol, and the meaning it carries in English, predates Graeco-Roman times.

The furthest back I've gotten so far isn't very far back at all. From a court transcript in 1877 or 1878:

Q: Place upon the blackboard the signs that you used in applications for insurance.
A: For what?
Q: Certain stenographic signs?
A: Yes, sir; there was the ordinary tick mark.
Q: Go and make them please; show what meant yes and show what meant no.
A: V is yes, and X, no.
Q: These signs have been the subject of a great deal of criticism in the courts of this State, haven't they?
A: Not that I know of.
Q: Is it not true that in Ohio a law has been passed forbidding the use of these signs?
A: I do not know.

Google Books also has some hits in a non-free document they date to "1746," but the wording and typography both lead me to believe that Google Books is just flat wrong about the date of this document.