Sinkhorn algorithm has been used pervasively to approximate the solution to optimal transport (OT) and unbalanced optimal transport (UOT) problems. However, its application in practice is limited due to its high computational complexity. To alleviate the computational burden, we propose a novel importance sparsification method, called Spar-Sink, to approximate regularized OT and UOT distances efficiently. Specifically, we leverage natural upper bounds for unknown optimal transport plans to construct effective sampling probabilities, and construct a sparse kernel matrix to accelerate Sinkhorn iterations, reducing the cost from O(n^2) to around O(n) for a sample of size n. Theoretically, we show the proposed estimators for the regularized OT and UOT distances are consistent under mild regularity conditions. Experiments on various synthetic datasets demonstrate Spar-Sink leads to smaller estimation errors compared with mainstream competitors.