In The Tragedie of Macbeth (around 1603), by the English poet and playwright William Shakespeare (1564-1616), Gray-Malkin is the name of a fiend in the shape of a grey she-cat, the cat being the form most generally assumed by the familiar spirits of witches according to a common superstition:

(Folio 1, 1623)
                               Actus Primus. Scœna Prima.
                    Thunder and Lightning. Enter three Witches.
1.When shall we three meet againe?
In Thunder, Lightning, or in Raine?
2. When the Hurley-burley’s done,
When the Battaile’s lost, and wonne.
3. That will be ere the set of Sunne.
1. Where the place?
2. Vpon the Heath.
3. There to meet with Macbeth.
1. I come, Gray-Malkin.
All. Padock calls anon:
faire is foule, and foule is faire,
Houer through the fogge and filthie ayre.
                                                                      Exeunt.

Similarly, in The Witch (circa 1613-16), the English poet and playwright Thomas Middleton (1580-1627) used the name Malkin to denote an evil spirit in the shape of a she-cat; the following lines are from the song Come away, come away, Hecate, which appears to have been interpolated into Macbeth during the printing of the First Folio:

A Spirit like a Cat descends
[…]
– Firestone: hark, hark, the Catt sings a braue Treble in her owne language.
– Hecate, going up. Now I goe, now I flie,
Malkin my sweete Spirit and I.

Malkin was a female forename composed of Mal, pet form of Maud (cf. Middle-English forms such as Mald and Mold), and the diminutive suffix -kin. The following is from the English-Latin dictionary Promptorium parvulorum sive clericorum (Storehouse for Children or Clerics – around 1440):

(1853 edition)
Malkyne, or Mawt¹, propyr name: Matildis².

(variants in manuscripts and early editions: ¹ Molt and Mawde, ² Matilda)

The forename Maud therefore represents Matilda. According to David Pickering in Dictionary of First Names (Penguin – 2004), Matilda is

from the Old German Mahthildis, itself from macht, might, and hiltja, battle, and thus meaning mighty in battle.

Malkin was used as a typical name, usually derogatory, for a lower-class woman, especially a servant or country girl. In The Tragedy of Coriolanus (around 1608-09) for example, Shakespeare makes Brutus say the following to Sicinius about Coriolanus:

(Folio 1, 1623)
All tongues speake of him, and the bleared sights
Are spectacled to see him. Your pratling Nurse
Into a rapture lets her Baby crie,
While she chats him: the Kitchin Malkin pinnes
Her richest Lockram ’bout her reechie necke,
Clambring the Walls to eye him.

The word was also used to denote a mop or bundle of rags used to wipe the floor, clean out an oven, etc. The following is from the above-mentioned Promptorium parvulorum sive clericorum:

Malkyne, mappyl³, or oven swepare: Dossorium, tersorium.

(³ mappyl = mapple, an obsolete noun meaning a mop)

Among the other meanings of malkin were a scarecrow but also a cat, as in Middleton’s play. In A Glossary of words used at Whitby and in the neighbourhood (1876), Francis Kildare Robinson (1809-82) wrote:

Mawkin, or Malkin, a cat. The mop for cleaning the baker’s oven. A scarecrow.

Following Shakespeare’s coinage, grimalkin was used in the sense of a cat by the English poet and Thames waterman John Taylor (1578-1653), known as the Water-Poet. For instance, this is what he wrote in a poem titled To the hopefull Paire of Brethren, and my worthy Patrones, Master Richard, and George Hatton, Loue, Learning, and true Happinesse, published in 1630:

Your Muses, th’one a Youth, and one an Infant,
Gaue me two Panegericks at one Instant:
The first Pen, the first line it pleas’d to walke in,
Did make my* Art a Rat, and like Grimalkin,
Or a kinde needfull Vermin-coursing Cat,
By Art I play, but will not eate your Rat.
I thanke you that you did so soone determine,
To Anagram my Art into a Vermine,
For which I vow, if e’re you keepe a Dayrie,
Of (now and then) a Cheese I will impaire yee.
* This Gentleman was pleased Anagrammatically to call me Water Rat, or water Art, which I doe Anagrammatize Water Rat, to bee A true Art.

The word grimalkin was especially used to denote a she-cat, as in this letter that the English naturalist and ornithologist Gilbert White (1720-93) wrote to the English lawyer and naturalist Daines Barrington (1727/8-1800) on 9^th May 1776:

My friend had a little helpless leveret brought to him, which the servants fed with milk in a spoon, and about the same time his cat kittened and the young were dispatched and buried. The hare was soon lost, and supposed to be gone the way of most fondlings, to be killed by some dog or cat. However, in about a fortnight, as the master was sitting in his garden in the dusk of the evening, he observed his cat, with tail erect, trotting towards him, and calling with little short inward notes of complacency, such as they use towards their kittens, and something gamboling after, which proved to be the leveret that the cat had supported with her milk, and continued to support with great affection.
Thus was a graminivorous animal nurtured by a carnivorous and predaceous one!
Why so cruel and sanguinary a beast as a cat, of the ferocious genus of Feles, the murium leo, as Linnæus calls it, should be affected with any tenderness towards an animal which is it’s [sic] natural prey, is not so easy to determine.
This strange affection probably was occasioned by that desiderium, those tender maternal feelings, which the loss of her kittens had awakened in her breast; and by the complacency and ease she derived to herself from the procuring her teats to be drawn, which were too much distended with milk, till, from habit, she became as much delighted with this foundling as if it had been her real offspring.
This incident is no bad solution of that strange circumstance which grave historians as well as the poets assert, of exposed children being sometimes nurtured by female wild beasts that probably had lost their young. For it is not one whit more marvellous that Romulus and Remus, in their infant state, should be nursed by a she-wolf, than that a poor little sucking leveret should be fostered and cherished by a bloody grimalkin.

The word has also been used to designate a jealous or imperious old woman. For instance, in The Young Philosopher (1798), by the English poet and novelist Charlotte Smith (1749-1806), Mrs Crewkherne, the hero’s aunt, a woman motivated by reactionary political beliefs, religious fanaticism and greed, is described by the hero’s brother as “the venerable old grimalkin”.

This sense explains the use of grimalkin as a verb in The World (London) of 15^th July 1756:

I am not henpecked; I am not grimalkined;  I have no Mrs. Freeman with her Italian airs; but I have a wife more troublesome than all three, by a certain ridiculous and unnecessary devotion that she pays to her father, amounting almost to idolatry.