Historically, the prefix "a-" derives from a preposition that was used before the gerund form of a verb. Johan Elsness cites an example of this in his paper On the progression of the progressive in early Modern English from Old English:
... yrstandæ ic wæs on huntune ... . (From Ælfric, Colloquy 68) 
In the above quote, "huntune" is the gerund of the verb "hunt"; the sentence as a whole essentially means, "Yesterday I was hunting".
The construction "on + gerund / progressive" then evolved into the form with the prefix "a-":
In Middle English similar constructions began to be common with just a light a before the main verb, as in ‘He was a-hunting.’, generally seen as a remnant of the full preposition.
If the preposition was not only reduced but dropped altogether, there was no longer any formal difference between the two constructions: that with BE followed by the present participle, and that with BE followed by the gerund, now without any intervening preposition.
(The uppercase "BE" simply refers to forms of the verb "be".)
Based on this, the "a-" prefixed to the -ing-forms in Herrick's poem does not have any special meaning. However, it does help with the metre: we would not have regular iambs if Herrick had written, "Old Time is still flying".
The "a-" could also be used without a hyphen, for example in the First Folio text of Shakespeare's The Taming of the Shrew, Act 3, scene 1:
Lucentio that comes a wooing
Modern editions of the play typically add the hyphen.
C. T. Onions notes in A Shakespeare Glossary (revised by Robert D. Eagleson, Oxford University Press, 1986) that
a before a gerund is a reduced form of 'on'
This is consistent with what Johan Elseness writes.
 The linked PDF version of the paper has "ZyrstandæZ ic wæs on huntunZe", which looks like some sort of conversion error.