The Media Post Type is limitedly integrated with Toolset Views.
While you can query them, most of the times doing so is not what you will need, because in the output it's very limited, also due to WordPress's management of Attachments, which is, slightly said, particular.
This is just as a general heads up.
It is most of the times better to create a post type and attach the images as fields, so to query them later thru the post type, not thru the media type itself.
Anyway, related to the issue you describe, I do not exactly understand the part of the Widget.
It seems to me, you added the Custom Search to the Widget, but the Results to a Post Body.
Is this correct?
I tried to set such a View locally and it worked.
1. I created a View for Media
2. Paginated it
3. Added a Custom Filter
4. Called the results thru the Widget on another page
5. I can paginate correctly.
==> Does the issue also persist with a WordPress Default Theme and NO Plugins BUT the Toolset Plugins?
If not, could you then re-enable the Plugins one after the other, and check the issue each time you enable a plugin?
Please report me when the issue comes back
==> It might also be due to the Theme.
Please do reactivate your Theme only after you are sure the issue isn't coming from a 3rd Party Plugin.
If all this fails - does it still happen with my above exact steps?
If not, how do your steps differ from mine?
According to this, I can then help you to solve the issue or eventually report it to the DEV.