It looks like you want to watch for query, not param:

watch: { 
  '$route.query.search': function(search) {
    console.log(search)
  }
}

When watching on the query you also do not need a deep: true as suggested as well in this StackOverflow. deep: true seems to work, but it is actually no the correct solution.