Some table_handling tools for lua
What is truthmap trying to achieve? I can't quite figure it out, sorry. 

contains by nature will always be O(N) in your implementation, so yes, it's speed is equal to the number of elements in your table. 

count should probably be renamed to countOf to better signify it's intent. Better yet, you could rename it where, have it take a function, and then allow the user to use the standard # operator on the resultant table.

removePerValue seems unnecessary with a where function. Users can simply filter the table rather than remove values from the table.

equalsAll in my opinion again should take a function as an argument and not an object.

You should change your loops from for k, v in pairs(tbl) do to for _, v in pairs(tbl) do if you are not using k.

I'm sure there's things to be said about the implementation of equalsAll but I don't have time to point that out at the moment.

Do you know about the # operator? appending # to the front of a table will return a value of the size of the table (more precisely, it will return the highest indexed number in the table, so it will be incorrect for sparse arrays).

You should ideally not need comments to explain the purpose of code - your functions should describe themselves ;-)