Maynes dates and dates of occupancy of various addresses in Belfast are:

Mayne, Alexander, 1852-1887
A Mayne 36 High Street (Slater Ulster 1852)
Alexander Mayne, 7½ High Street (1854-67) (Neilands)
34 High Street        1852 (QUB xff Z152/1/BROADSIDES)
7 1/2 High Street 1854 – 67 (QUB xff Z152/1/BROADSIDES)
        +Corporation Street 1868 (QUB xff Z152/1/BROADSIDES)
        Died 1887 (QUB xff Z152/1/BROADSIDES)
The sources of these dates and locations are documented in my thesis "The printed ballad in Ireland: a guide to the popular printing of songs in Ireland, 1760-1920" (NUI Galway, 2006). Mayne suceeded Joseph Smyth in 34 High Street in 1852. A possible confusions exists which I state in the thesis:
"Martin's Directory 1841-2 gives a Mayne, Alex. S, Collector of Water Tax, Publisher &c, 1 Donegal Square East (alphabetical) and lists him also, under Trades, as Bookseller and Stationer at the same address. I conjecture this is a different Mayne, perhaps the ballad printer's father. The British Library has a single item published by A. S. Mayne in 1852 when Alex Mayne was succeeding Joseph Smyth at 34 High Street. Care is needed to distinguish between them."