Here you go folks....after a bit of Googling (and thanks for the original query, Anonsi, otherwise I'd probably never have known this!)
In 1828 the Sydney newspaper, the Monitor, reported a street fight that had occurred in Sydney on Saint Patrick’s day. The report included the comment that following the fight ‘many a piteous Shela stood wiping the gory locks of her Paddy’. This is the earliest written evidence of the use of the Australian word sheila. The Oxford English Dictionary defines sheila as ‘a young girl or young woman; agirlfriend. Playfully affectionate and predominantly in male use’. The OED also includes the Irish origin of the word:
It may represent a generic use of the (originally Irish) personal name Sheila, the counterpart of Paddy...in any case, it became assimilated to this at some later stage.
We can detect some uncertainty in the OED commentary on the word sheila; a sense that some information does not fit, that something is missing. More recently, the author of The Dinkum Dictionary, Susan Butler, is confident that
‘Sheila’ was a common female name in Ireland, used alongside the name ‘Paddy’ to represent the archetypal Irish couple. From this early usage (dating from the 1820s in Britain) ‘Sheila’ came to mean any female, whether Irish or not. This British use of ‘sheila’ was then transported to the colonies.