When were verses invented in the Hebrew Bible?

 First thing to note is that verses are absolutely present in the Aleppo Codex and earlier manuscripts containing the te'amim.

The New testament verse divisions are much later as indicated anecdotally by Bart Ehrman recently. But the precedent is set for division of verses as early as the musical accents of the Hebrew Bible were introduced. 

Numbering them is a different issue. But there is little doubt that they have been there for the music from at least this time and I suspect considerably earlier.

Ex 20:7 part of the Codex Babylonicus Petropolitanu dated 916 CE

Music defines the verses in the Old Testament. This is an absolute rule.

The Karaites also used the te'amim in the Arabic versions of the Hebrew Bible. Here is part of  a fragment of Exodus (chapter 1:1-8:5) written in Arabic characters - directly transcribed from the Hebrew.

Karaite ms - note the clear te-amim - 10th c CE