I use Gmail at the office strictly for work and I use Google Maps for personal use on my iPhone. It seems that my personal search history on Google Maps is now linked to my work Gmail account. How do I sever this tie? I don't use Gmail on my phone, only on a laptop at work.
Google Maps and Gmail are simply two of the products which Google makes available to you via your Google account.
Make yourself a second, personal Google account. Quite possibly the simplest tool to do this in is Gmail, since every Google account does need to have a working email account associated with it. Set it up on your phone (you don't have to use it, just set it up and receive any messages that Google sends you on it). Remove your work Gmail account from your phone.