The latest Firefox update (43.0 for Linux Mint) disables the mint-search-addon automatically. As I understand it, the add on identifies the browser as part of a Linux Mint installation but doesn't do much else. Google pays LM for the search requests. Not sure how this is going to play out but it looks like Firefox have taken against LM. Suspect LM will upgrade it to meet Firefox' requirements, but interesting that the LM update manager includes the new Firefox as a recommended update.
From what I can make out, the mint-search-addon is linked to other bits of mint. Attempting to remove it:
sudo apt-get remove mint-search-addon
Produces the the following as part of the output:
The following packages will be REMOVED
mint-meta-core mint-meta-xfce mint-search-addon
Don't think it would be a good idea to remove it.