Let $M$ be a finite dimensional smooth manifold and $M=\bigcup_{i\in I}U_i$ an open cover of $M$.
Does there exist a finite open cover $M=\bigcup_{k=0}^l V_k$, such that each $V_k$ is the disjoint union of open subsets $V_k=\bigcup_{j\in J}V_{k,j}$ and each $V_{k,j}$ lies in one $U_i$?
I tried to attack this problem with the help of a triangulation, such that all simplices lie in one $U_i$, but was not succesful.
Your idea of using a triangulation each of whose simplices lies in one of the $U_i$ is a good one.
There exists such a covering of the form $V_0 \cup \ldots \cup V_D$ where $D$ is the dimension of $M$, such that if $M^{(k)}$ denotes the $k$-skeleton of the triangulaion then $$M^{(k)} \subset V_0 \cup \ldots \cup V_k \quad\text{for each $k=1,\ldots,D$.} $$ In fact all that one uses for this construction is that $M$ is a locally finite simplicial complex of dimension $D$.
Start with $V_0$ being a disjoint union of neighborhoods of the $0$-simplices, each contained in one of the $U_i$. This can be done constructively using barycentric coordinates in each simplex.
Suppose by induction that $V_0,\ldots,V_{k-1}$ have been constructed. Consider a $k$-simplex $\sigma$, and let $\partial\sigma$ denote its boundary by which I just mean its $k-1$ skeleton. By induction the $k-1$-skeleton of $\sigma$ is contained in $V_0 \cup \cdots \cup V_{k-1}$, and so the set $$\sigma^* = \sigma - (V_0 \cup \cdots \cup V_{k-1}) $$ is an open subset of $\sigma - \partial\sigma$. The sets $\sigma^*$ are pairwise disjoint as $\sigma$ varies over the $k$-simplices in $M$. So we can fatten up each $\sigma^*$ to an actual open subset $\sigma^{**}$ of $M$, keeping them pairwise disjoint; this is not hard to do concretely using barycentric coordinates of the simplices that contain $\sigma^*$. Also, since the whole of $\sigma$ is contained in some $U_i$, and since we need only fatten $\sigma^*$ up an arbitrarily small amount (as measured using barycentric coordinates), we may assume that $\sigma^{**}$ is contained in some $U_i$. Then define $V_k$ to be the union of the sets $\sigma^{**}$ over all $k$-simplices $\sigma$.