As far as I know I am the first researcher to uncover the surname of John Phips' wife who is listed simply as 'Mary' in all other genealogies I have seen of the family. Here is how I was able to find the surname with the assistance of an Underwood family descendant.

What I knew about 'Mary' was that she is said to be buried in Medway, Massachusetts with a death recorded in 1754 at age 82 - making her birth about 1672 (Medway Vital Records).
The History of Reading, and other genealogies of the Phipps family, state that the wife of John Phips was born in Reading.  John and Mary's first children were born in Reading according to vital records there.
I had also found that John Phips (b. 1696-1699, son of Mary and John) of Sherborn was named as 'grandson' of a William Bull of Sherborn in a 1719 document (this also has not been recorded in any of the published Phips genealogies to my knowledge). A search for the children of William Bull's first marriage to Abiah Perry in 1673 yielded no daughter Mary in vital records, or in the 1719 document where he names other children, suggesting that he had no daughter Mary living at the time, whereas Mary, wife of John Phips, lived until 1754.
The search also revealed that William Bull had no known children by his second wife Elizabeth ______  Underwood.  Elizabeth's first husband had been Joseph Underwood whom she married in 1671.  He died in 1692.  I had found children of Joseph and Elizabeth born at Watertown, but no daughter Mary. However an Underwood researcher mentioned that right after Elizabeth and Joseph's  marriage they resided for a short time at Reading where only one child was born to them, a daughter Mary, born June 13, 1673!!  They then went back to Watertown and were the parents of numerous other children.  The Genealogy of the Underwood Family by Lucien Underwood says that the daughter Mary born in 1673 to Elizabeth and Joseph Underwood probably died young.  Yet no death occurs for her in the Reading or Watertown records, and according to a contradiction in the same Underwood Genealogy, Joseph Underwood's will dated in 1692 lists an inheritance for  his "four daughters"  which by my count would have to include the daughter Mary, who would have been abt 18. The Underwood genealogy does not name the "four daughters" but when I checked Joseph Underwood's will, a daughter Mary was named.  In all probability she was still alive when her mother Elizabeth married William Bull in 1693.
So...when William Bull married Elizabeth Underwood in 1693, the  children of Elizabeth's
1st marriage became William's (step)children, and as follows, the grandchildren of Elizabeth by her marriage to Joseph, became his (step) grandchildren. Therefore, a child born to Mary Underwood (born in 1673), would be the (step) grandchild of William Bull.

So: Mary, wife of John Phips was said to have been born abt 1672 - Mary Underwood was born in 1673. (Reading VR)
Mary, wife of John Phips was said to be born at Reading - Mary Underwood was born at
Reading. (Reading VR)
John and Mary Phips had a child John that was called grandson of William Bull - Mary Underwood's children by her marriage would be called grandchildren to William Bull on his marriage to Mary's mother Elizabeth Underwood.
Deductive reasoning  would point to the fact that Mary Underwood was probably the wife of our John Phips born in December of 1668.
The only thing needed to confirm this would be a marriage record for John and Mary Underwood. As yet no marriage record has been found for John and Mary in Reading, Watertown or surrounding towns, nor in Wrentham, Medway (where they later lived) or Woburn where another child or two was born.  However, given the fact that Mary Underwood was born at the appropriate time, in the appropriate place, and was stepchild to William Bull (making her children his step grandchildren), I would say it is pretty likely this is our Mary!